题意：
给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;
}