POJ3420 Quad Tiling (矩阵加速状压dp）

Quad Tiling

Time Limit: 1000MS		Memory Limit: 65536K

Description

Tired of the Tri Tiling game finally, Michael turns to a more challengeable game, Quad Tiling:

In how many ways can you tile a 4 × N (1 ≤ N ≤ 10⁹) rectangle with 2 × 1 dominoes? For the answer would be very big, output the answer modulo M (0 < M ≤ 10⁵).

Input

Input consists of several test cases followed by a line containing double 0. Each test case consists of two integers, N and M, respectively.

Output

For each test case, output the answer modules M.

Sample Input

Sample Output

1
11
95

Source

POJ Monthly--2007.10.06, Dagger

这题是POJ2411的放大版。。记得JSOI2013第一轮考过一题5*N的。。当时cxt还和我炫耀。。现在看看还是很简单的

N=1e9 M=1e5的时候。。需要longlong，不过我侥幸没加longlong过了。。

做法就是开个16*16的矩阵。。不过根据矩阵似乎就可以直接推出来递推式了。。好神orz...

Codes:

 1 #include<set>
 2 #include<queue>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<iostream>
 7 #include<algorithm>
 8 using namespace std;
 9 #define For(i,n) for(int i=1;i<=n;i++)
10 #define Rep(i,l,r) for(int i=l;i<=r;i++)
11 
12 struct Matrix{
13     int A[17][17];
14     Matrix(){
15         memset(A,0,sizeof(A));
16     }
17 }Unit,Ans,TAns;
18 
19 int opt[20],n,Mod;
20 
21 Matrix operator * (Matrix A,Matrix B){
22    Matrix C;
23     Rep(i,0,15)
24       Rep(j,0,15)
25         Rep(k,0,15)
26            C.A[i][j] = ( C.A[i][j] + (A.A[i][k] * B.A[k][j]) % Mod ) % Mod;
27     return C;
28 }
29 
30 bool Check(int s1,int s2){
31     if((s1|s2)!=15) return false;
32     for(int i=0;i<=15;){
33         if( (s1&(1<<i)) != (s2&(1<<i)) ) i++;
34         else{
35             if(i==15) return false; else
36             if(  ( s1 & (1<<(i+1)) ) != ( s2 & (1<<(i+1)) ) ) return false;
37             i+=2;
38         }
39     }
40     return true;
41 }
42 
43 int main(){
44     Rep(i,0,15){
45         Rep(j,0,15)
46             if(Check(i,j)) Ans.A[i][j] = TAns.A[i][j] = 1;
47         if(Check(i,15)) 
48             opt[i] = 1;
49     }
50     while(scanf("%d%d",&n,&Mod),Mod+n){        
51         Rep(i,0,15){
52             Rep(j,0,15){
53                 Ans.A[i][j] = TAns.A[i][j];
54                 Unit.A[i][j] = 0;
55             }
56             Unit.A[i][i] = 1;
57         } 
58         while(n){
59             if(n&1) Unit = Unit * Ans;
60             Ans = Ans * Ans;
61             n = n >> 1;
62         }
63         int ans = 0;
64         Rep(i,0,15) 
65             ans = (ans % Mod + (opt[i] * Unit.A[0][i] % Mod) % Mod) % Mod;
66         printf("%d
",ans);
67     }
68     return 0;
69 }