题意
n*4的格子，用1*2和2*1的砖块覆盖。问方案数(mod 1e9+7)。（n不超过1e9）
题解
递推了个式子然后错位相减。
f[n] =f[n-1]+4f[n-2]+2f[n-3]+3f[n-4]+2f[n-5]+2f[n-6]+..+(x%2?2:3)f[n-x] f[n-2]= f[n-3]+4f[n-4]+2f[n-5]+3f[n-6]+..+(x%2?2:3)f[n-x] f[n] =f[n-1]+5f[n-2]+ f[n-3]-f[n-4] 再用矩阵快速幂。 另外，这题可以先用暴力的dfs或者状态压缩dp求得前几项，然后套得出递推式。 不过，官方题解的方法是状态压缩加矩阵快速幂优化： 只考虑一列的状态，0表示没有被覆盖，1表示被覆盖了，只可能有0000，1111，1001，0110，1100，0011。 dp[i][j]表示前i-1列覆盖满，第i列状态为j的方案数。考虑转移,然后a[i][j]==1就是状态i可以由状态j转移过来，那么就可以矩阵快速幂加速了。--
51nod 上的，类似。a数组可以dfs出来。代码
typedef long long ll;typedef vectorVI;typedef vector Mat;const ll mod=1000000007;Mat mul(Mat &a,Mat &b){ Mat c(SZ(a), VI(SZ(b[0]))); rep(i,0,SZ(a))rep(j,0,SZ(b[0]))rep(k,0,SZ(b)) c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod; return c;}Mat qpow(Mat a,ll b){ Mat c(SZ(a), VI(SZ(a))); rep(i,0,SZ(a))c[i][i]=1; for(;b;b>>=1,a=mul(a,a))if(b&1)c=mul(c,a); return c;}int main(){ Mat a(4,VI(4)); a[0]=VI{1,5,1,-1}; rep(i,0,3)a[i+1][i]=1; ll n; while(~scanf("%lld",&n)){ if(n==1)puts("1"); else if(n==2)puts("5"); else if(n==3)puts("11"); else if(n==4)puts("36"); else{ Mat c=qpow(a,n-4); printf("%lld\n",((c[0][0]*36+c[0][1]*11+c[0][2]*5+c[0][3])%mod+mod)%mod); } } return 0;}
状态压缩
int main() { Mat a(6,VI(6)); a[0]=VI{1,1,1,1,1,0}; a[1]=VI{1,0,0,0,0,0}; a[2]=VI{1,0,0,1,0,0}; a[3]=VI{1,0,1,0,0,0}; a[4]=VI{1,0,0,0,0,1}; a[5]=VI{0,0,0,0,1,0}; ll n; while(~scanf("%lld",&n)){ printf("%lld\n",qpow(a,n)[0][0]); } return 0;} 骨牌覆盖 V2
const int N=1<<5;int n,m;Mat a(N,VI(N));void dfs(int c,int pre,int cur){ if(c>n)return; if(c==n){ ++a[pre][cur]; return; } dfs(c+1,pre<<1,cur<<1|1);//竖着放 dfs(c+1,pre<<1|1,cur<<1);//不能放 dfs(c+2,pre<<2,cur<<2);//横着放}int main() { while(~scanf("%d%d",&m,&n)){ rep(i,0,SZ(a))rep(j,0,SZ(a[i]))a[i][j]=0; dfs(0,0,0); printf("%lld\n",qpow(a,m)[0][0]); } return 0;}