题意：
给4*n(n<10^9)的大矩形，问有多少种用1*2的小矩形填满的方案。
分析：
又是铺瓷砖，不过这次n太大，，不能再一个一个格的dp了。可以先算出相邻两行的状态转移，再用矩阵来加速n行的状态转移。
代码：
//poj 3420//sep9#include <iostream>using namespace std;const int maxN=16;struct MATRIX{__int64 m[maxN][maxN];}mat;int n,mod;void dfs(int l,int now,int pre){if(l>4) return;if(l==4){++mat.m[pre][now];return ;}dfs(l+1,(now<<1)|1,pre<<1);dfs(l+1,now<<1,(pre<<1)|1);dfs(l+2,(now<<2)|3,(pre<<2)|3);}MATRIX mul(MATRIX a,MATRIX b) {MATRIX c;memset(c.m,0,sizeof(c.m));for(int i=0;i<16;++i)for(int j=0;j<16;++j)for(int k=0;k<16;++k){c.m[i][j]+=a.m[i][k]*b.m[k][j];c.m[i][j]%=mod;}return c; }MATRIX expo(MATRIX a,int k) {if(k==1)return a;MATRIX e;memset(e.m,0,sizeof(e.m));for(int i=0;i<16;++i){e.m[i][i]=1;}if(k==0)return e;while(k){if(k&1)e=mul(a,e);a=mul(a,a);k>>=1;}return e; } int main() {memset(mat.m,0,sizeof(mat.m));dfs(0,0,0);while(~scanf("%d%d",&n,&mod)){if(!n&&!mod)break;if(mod==1){printf("0\n");continue;}MATRIX ans=expo(mat,n);printf("%I64d\n",ans.m[15][15]);}return 0; }
人生就是要感受美丽的、善良的，丑恶的、病态的。
