2010年02月17日星期三.sgu197 矩陣快乘 + 高精除法 + 狀態(tài)dp
sgu197:矩陣快乘 + 高精除法 + dp
題目中的m范圍如此之小，一看就有問題,很容易想到狀態(tài)壓縮。
兩行之間的不同狀態(tài)表示，可以用矩陣表示兩行的狀態(tài)轉移。
矩陣中的元素為1，表示兩行狀態(tài)可達，元素為0 ，表示狀態(tài)非法，也就是兩行狀態(tài)不可達。
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 如果再在矩陣的右側乘以一個列向量，每個元素是能到達這個元素所表示狀態(tài)的染色方法種數，
那么乘得的一個列向量所表示的就是新的能到達新的一行的各種狀態(tài)的種數。
很容易想到，對于題目中所提到的n，和轉移矩陣M,
所求的結果也就是 M^(n-1) 再乘以一個全一的初始狀態(tài)列向量,再求出所有元素的和即可。
而對于題目中提到的巨大的n，可以使用二分矩陣乘法來處理。
所以最后的復雜度也就是 ，矩陣乘法的復雜度*二分的復雜度。
最大的計算量 = 32 * 32 * 32 * log(10^100) = 3276800,兩秒的時間，夠了。
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://m.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