POJ3420 Quad Tiling (矩阵加速状压dp）-白红宇

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

阅读量：6239 次

发布时间：2019-06-22

本文共 1671 字，大约阅读时间需要 5 分钟。

Quad Tiling

Time Limit: 1000MS		Memory Limit: 65536K

Description

Tired of the 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

1 100003 100005 100000 0

Sample Output

Source

, Dagger

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

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

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

Codes:

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              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<
             
              > 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\n",ans);67 }68 return 0;69 }