| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 3495 | Accepted: 1539 |
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 0
Sample Output
1 11 95
Source
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define ll long long #define N 10 int MOD; struct Matric { int size; int a[N][N]; Matric(int s=0) { size=s; memset(a,0,sizeof(a)); } Matric operator * (const Matric &t) { Matric res=Matric(size); for(int i=0;i<size;i++) { for(int k=0;k<size;k++) { if((*this).a[i][k]) for(int j=0;j<size;j++) { res.a[i][j]+=(ll)(*this).a[i][k]*t.a[k][j]%MOD; res.a[i][j]=(res.a[i][j]+MOD)%MOD; } } } return res; } Matric operator ^ (int n) { Matric ans=Matric(size); for(int i=0;i<size;i++) ans.a[i][i]=1; while(n) { if(n&1) ans=ans*(*this); (*this)=(*this)*(*this); n>>=1; } return ans; } void debug() { for(int i=0;i<size;i++) { for(int j=0;j<size;j++) { printf("%d ",a[i][j]); } printf("\n"); } } }; int main() { int n; while(scanf("%d%d",&n,&MOD),n||MOD) { Matric a=Matric(4); Matric b=Matric(4); a.a[0][0]=1; a.a[0][1]=1; a.a[0][2]=5; a.a[0][3]=11; b.a[0][3]=-1; b.a[2][3]=5; b.a[1][0]=b.a[2][1]=b.a[3][2]=b.a[1][3]=b.a[3][3]=1; b=b^n; a=a*b; printf("%d\n",(a.a[0][0]+MOD)%MOD); } return 0; }
原文：http://www.cnblogs.com/hate13/p/4471465.html