poj 3420 Quad Tiling

Quad Tiling

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4406		Accepted: 2011

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

题意：在4*N的方格内塞满规格是1*2的砖头，横放竖放都可以，问一共有多少种放法。
思路：

设f(n,state)：第n列铺砖状态为state时的情况数，状态state可以是：(0代表还未铺砖，1代表已被砖占据):
 state 0:0
         0
         0
         0
 state 1:1
         1
         0
         0
或者     
         0
         0
         1
         1
 state 2:
         1
         0
         0
         1
 state 3:
         0
         1
         1
         0
 state 4:
         1
         1
         1
         1
需要用到的情况就这么多，为什么呢，举个例子

先写出四行三列的格子，其中定义状态：
0      1     2     3    ...   14     15
X00   XX0   X00   XX0         X00    XX0
X00   X00   XX0   XX0         XX0    XX0
X00   X00   X00   X00         XX0    XX0
X00   X00   X00   X00         XX0    XX0
为考虑第2列的所有状态，其中x代表已被填满，0代表还是空的

再定义：
 0      1      2      3     ...   14     15
XX0    XXX    XX0    XXX          XX0    XXX
XX0    XX0    XXX    XXX          XXX    XXX
XX0    XX0    XX0    XX0          XXX    XXX
XX0    XX0    XX0    XX0          XXX    XXX

为考虑第三列的所有状态

那么第三列中状态0可以由第2列中的哪些状态转化而来呢？显然第2列的状态0，3，9，12，15可以通过铺砖得到第三列的状态0；
而计算状态0转移过程所需要用到的状态0，3，9，12，15可以由那些状态转移得到呢？除了状态9需要用到前一列的状态0和6得到，其他状态都可以互推，不需要新的状态。
那么需要用到的状态就是一开始所说的那几种，并且转移方程可以写成如下递推式：

f(n+1, 0) = f(n, 0) + 2 * f(n, 1) + f(n, 2) + f(n, 4)
 f(n+1, 1) = f(n, 0) + f(n, 1)
 f(n+1, 2) = f(n, 0) + f(n, 3)
 f(n+1, 3) = f(n, 2)
 f(n+1, 4) = f(n, 0)
写成矩阵的形式：(f(n+1,0),f(n+1,1),f(n+1,2),f(n+1,3),f(n+1,4))=A*(f(n,0),f(n,1),f(n,2),f(n,3),f(n,4));
A=1 1 1 0 1
  2 1 0 0 0 
  1 0 0 1 0
  0 0 1 0 0
  1 0 0 0 0
B=A^N,B[0][0]即是第N列砖的铺砖的所有可能数。
AC代码：

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<queue>
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
typedef long long ll;
const int M_MAX = 100000;
mat A, B;
ll n;
int N, M;
mat mul(mat &A,mat &B,int &M) {
    mat C(A.size(),vec(B[0].size()));
    for (int i = 0; i < A.size();i++) {
        for (int k = 0; k < B.size();k++) {
            for (int j = 0; j < B[0].size();j++) {
                C[i][j] = (C[i][j]+A[i][k]*B[k][j]) % M;
            }
        }
    }
    return C;
}

mat pow(mat A,ll n){
    mat B(A.size(),vec(A[0].size()));
    for (int i = 0; i < A.size();i++) {
        B[i][i] = 1;
    }
    while (n>0) {
        if (n & 1)B = mul(B, A,M);
        A = mul(A, A,M);
        n >>= 1;
    }
    return B;
}

int main() {
    while (scanf("%d%d",&N,&M)!=EOF&&N) {
        mat A(5,vec(5));
    
        A[0][0] =A[0][1]=A[0][2]=A[0][4]=1;
        A[1][0] = 2; A[1][1] = 1;
        A[2][0] = A[2][3] = 1;
        A[3][2] = 1;
        A[4][0] = 1;
        A = pow(A, N);
        printf("%d
",A[0][0]);
    }
    return 0;
}