bzoj-2126: 排斥反应

Description

在一个圆上均匀分布p*q个点{A1，A2，A3…Ap*q}，Ai与Aj的距离为min{abs(i-j)，p*q-abs(i-j)}，在上面选任意个点(可以选0个)，如果选择的点中存在两个点距离为p或q，就会发生排斥反应，求不发生排斥反应的方案总数。

Input

输入的第一行包含两个整数，分别表示p和q

Output

输出一个整数，表示方案总数，由于这个题答案可能很大，只要输出答案mod 19921107

Sample Input

Sample Output

HINT
  
  这真是道神题，看范围像是状压DP，但完全不会，去看题解，真是太神了，把所有点之间的关系用一个P*Q的矩阵表示，则相邻的两

个点之间会发生排斥，所以问题转化为求从P*Q矩阵中选任意多个点两两不相邻的方案数为多少，预处理出状态间的转移系数，最后再

用矩阵快速幂加速就行了，注意矩阵的左右上下边界都是联通的。

/**************************************************************Problem: 2126User: WZJRJ28Language: PascalResult: AcceptedTime:29672 msMemory:1164 kb
****************************************************************/vari,j,k,tot,ans:longint;p,q,y:int64;jud:boolean;f:array [1..200] of int64;a,t,tt:array [1..200,1..200] of int64;
procedure dfs(k,z:int64);
beginif k>p thenbegininc(TOT);f[tot]:=z;exit;end;dfs(k+1,z);if (z and 1<>1)or(k<>p) then dfs(k+2,z+(1 shl (k-1)));
end;
beginread (p,q);dfs(1,0);for i:=1 to tot dofor j:=1 to tot doif f[i] and f[j]=0 then a[i,j]:=1;y:=q-1;if y=0 thenbeginwriteln(tot);exit;end;jud:=true;while y<>0 dobeginif y and 1=1 thenif jud thenbeginjud:=false;t:=a;endelsebeginfillchar (tt,sizeof(tt),0);for i:=1 to tot dofor j:=1 to tot dofor k:=1 to tot dott[i,j]:=(tt[i,j]+t[i,k]*a[k,j])mod 19921107;t:=tt;end;fillchar (tt,sizeof(tt),0);for i:=1 to tot dofor j:=1 to tot dofor k:=1 to tot dott[i,j]:=(tt[i,j]+a[i,k]*a[k,j])mod 19921107;a:=tt;y:=y shr 1;end;for i:=1 to tot dofor j:=1 to tot doif f[i] and f[j]=0 thenans:=(ans+t[i,j]) mod 19921107;writeln(ans);
end.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！