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 ≤ 109) rectangle with 2 × 1 dominoes? For the answer would be very big, output the answer modulo M (0 < M ≤ 105).
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 10000 3 10000 5 10000 0 0Sample Output
1 11 95Source
POJ Monthly--2007.10.06, Dagger 递推公式及矩阵，快速幂加速f[n]=f[n-1]+5*f[n-2]+f[n-3]-f[n-4]; LL a[4][4]={ {11, 5, 1, 1}, { 0, 0, 0, 0}, { 0, 0, 0, 0}, { 0, 0, 0, 0} }, c[4][4]={ { 1, 1, 0, 0}, { 5, 0, 1, 0}, { 1, 0, 0, 1}, {-1, 0, 0, 0} }; #include <iostream> #include <string> #include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <cmath> #include <vector> #include <queue> #include <stack> #include <set> #include <map> using namespace std; typedef long long LL ; typedef unsigned long long ULL ; const int maxn = 1000 + 10 ; const int inf = 0x3f3f3f3f ; const int npos = -1 ; const int mod = 1e9 + 7 ; const int mxx = 100 + 5 ; const double eps = 1e-6 ; LL m; struct Matrix{ LL a[4][4]; Matrix operator * (const Matrix B){ Matrix C; memset(&C,0,sizeof(C)); for(int k=0;k<4;k++) for(int i=0;i<4;i++) if(a[i][k]) for(int j=0;j<4;j++) if(B.a[k][j]) C.a[i][j]=((C.a[i][j] + (a[i][k]*B.a[k][j])%m)%m + m*2)%m; return C; } }; LL a[4][4]={ {11, 5, 1, 1}, { 0, 0, 0, 0}, { 0, 0, 0, 0}, { 0, 0, 0, 0} }, c[4][4]={ { 1, 1, 0, 0}, { 5, 0, 1, 0}, { 1, 0, 0, 1}, {-1, 0, 0, 0} }; LL cal(int k){ if(k>0){ Matrix e, f; for(int i=0;i<4;i++) for(int j=0;j<4;j++){ e.a[i][j]=a[i][j]; f.a[i][j]=c[i][j]; } while(k){ if(1&k){ e=e*f; } f=f*f; k>>=1; } return e.a[0][0]%m; }else{ return a[0][-k]%m; } } int n; int main(){ // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); while((~scanf("%d %lld",&n,&m)) && n>0){ printf("%lld\n",cal(n-3)); } return 0; }