2010年02月17日星期三.sgu197 矩陣快乘 + 高精除法 + 狀態(tài)dp
sgu197:矩陣快乘 + 高精除法 + dp
題目中的m范圍如此之小，一看就有問題,很容易想到狀態(tài)壓縮。
兩行之間的不同狀態(tài)表示，可以用矩陣表示兩行的狀態(tài)轉(zhuǎn)移。
矩陣中的元素為1，表示兩行狀態(tài)可達(dá)，元素為0 ，表示狀態(tài)非法，也就是兩行狀態(tài)不可達(dá)。
stat[0][0] stat[0][1] stat[0][2] stat[0][3]stat[1][0] 0 1 1 1 stat[1][1] 1 1 1 1 stat[1][2] 1 1 1 1 stat[1][3] 1 1 1 0 如果再在矩陣的右側(cè)乘以一個(gè)列向量，每個(gè)元素是能到達(dá)這個(gè)元素所表示狀態(tài)的染色方法種數(shù)，
那么乘得的一個(gè)列向量所表示的就是新的能到達(dá)新的一行的各種狀態(tài)的種數(shù)。
很容易想到，對(duì)于題目中所提到的n，和轉(zhuǎn)移矩陣M,
所求的結(jié)果也就是 M^(n-1) 再乘以一個(gè)全一的初始狀態(tài)列向量,再求出所有元素的和即可。
而對(duì)于題目中提到的巨大的n，可以使用二分矩陣乘法來處理。
所以最后的復(fù)雜度也就是 ，矩陣乘法的復(fù)雜度*二分的復(fù)雜度。
最大的計(jì)算量 = 32 * 32 * 32 * log(10^100) = 3276800,兩秒的時(shí)間，夠了。
1
2 const int M = 32;
3 #define bin(x) (1 <<(x))
4 int n,m,mod,mask;
5 struct Matrix {
6 int m[M][M];
7 Matrix(){memset(m,0,sizeof(m));}
8 Matrix operator = (Matrix b) {
9 for (int i = 0;i <= mask;i++) {
10 for (int j = 0;j <= mask;j++) {
11 m[i][j] = b.m[i][j];
12 }
13 }
14 return *this;
15 }
16 }org,bas,res;
17 Matrix mul(Matrix a,Matrix b)
18 {
19 Matrix c;
20 for (int i = 0;i <= mask;i++) {
21 for (int j = 0;j <= mask;j++) {
22 for (int k = 0;k <= mask;k++) {
23 c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
24 }
25 }
26 }
27 return c;
28 }
29
30 char s[512];
31 int d[512],len;
32 int two[2048],top;
33
34 void div() {
35 int i,j,k,left = 0;
36 for (i = len - 1;i >= 0;i--,left *= 10) {
37 int tmp = d[i] + left;
38 if (tmp < 2) {
39 left = d[i];
40 d[i] = 0;
41 }else {
42 d[i] = tmp / 2;
43 left = tmp % 2;
44 }
45 }
46 while (d[len - 1] == 0 && len > 0) { len--; }
47 }
48
49 void pre()
50 {
51 int i,j,k;
52 len = strlen(s);
53 for (i = 0;i < len;i++) { d[len - 1 - i] = s[i] - '0'; }
54 while (len > 0) {
55 two[top++] = d[0] % 2;
56 div();
57 }
58 mask = bin(m) - 1;
59 for (i = 0;i <= mask;i++) {
60 for (j = 0;j <= mask;j++) {
61 int tmp = i&j;
62 if ((tmp&3) == 3 || (tmp&6) == 6 ||
63 (tmp&12) == 12 || (tmp&24) == 24) { continue; }
64 tmp = (~i & ~j) & mask;
65 if ((tmp&3) == 3 || (tmp&6) == 6 ||
66 (tmp&12) == 12 || (tmp&24) == 24) { continue; }
67 org.m[i][j] = 1;
68 }
69 }
70 }
71 //http://www.shnenglu.com/schindlerlee
72 int main()
73 {
74 int i,j,k;
75 scanf("%s %d %d",s,&m,&mod);
76 pre();
77 if (len == 1 && s[0] == '1') {
78 printf("%d\n",bin(m));
79 return 0;
80 }
81 for (i = 0;two[i] == 0;i++);
82 for (two[i] = 0,j = 0;j < i;j++ ) {
83 two[j] = 1;
84 }
85 while (two[top-1] == 0) { top--; }
86
87 bas = org;
88 for (i = 0;i <= mask;i++) { res.m[i][i] = 1; }
89 for (i = 0;i < top;i++) {
90 if (two[i]) {
91 res = mul(res,bas);
92 }
93 bas = mul(bas,bas);
94 }
95 int ans = 0;
96 for (i = 0;i <= mask;i++) {
97 for (j = 0;j <= mask;j++) {
98 ans = (ans + res.m[i][j]) % mod;
99 }
100 }
101 printf("%d\n",ans);
102 return 0;
103 }
104
105