题意：
用1*2的骨牌铺满4*n的矩形总共有多种方法
经典题：可见骨牌铺方格的多种做法
因为宽只有4，考虑先求递推式，假设当前长度为x，有：
①长度为x-1的所有情况后面竖着放2个骨牌，f(x) += f(x-1)
②长度为x-2的所有情况后面横着放4个骨牌或者横着放2个，竖着放2个，而后者又有三种不同放法，f(x) += 4f(x-2)
③长度为x-3的所有情况后面横着放4个，竖着放2个，去掉和②重复的有2种情况，f(x) += 2f(x-3)
④长度为x-4的所有情况后面横着放6个，竖着放2个，去掉和②③重复的有3种情况，f(x) += 3f(x-4)
……（这里建议纸上画一画）
最后可以发现规律得到公式
将f(n)和f(n-1)相加有
这样就可以转成矩阵了
然后就可以愉快的快速幂了
#include<stdio.h> #include<string.h> #define mod 1000000007 #define LL long long LL q[6] = {0,5,2,1,1}; typedef struct { LL i, j; LL a[6][6]; void init() { memset(a, 0, sizeof(a)); a[1][4] = a[2][1] = a[2][2] = a[3][1] = a[4][3] = 1; a[1][2] = 5; } void unit() { memset(a, 0, sizeof(a)); for(i=1;i<=4;i++) a[i][i] = 1; } }Matrix; Matrix Jz; Matrix Powto(Matrix p, LL k); Matrix Jjcf(Matrix p1, Matrix p2); int main(void) { LL i, n, ans; while(scanf("%lld", &n)!=EOF) { if(n==1) printf("1\n"); else if(n==2) printf("5\n"); else { Jz.init(); Jz = Powto(Jz, n-2); ans = 0; for(i=1;i<=4;i++) ans = (ans+q[i]*Jz.a[1][i])%mod; printf("%lld\n", ans); } } return 0; } Matrix Powto(Matrix p, LL k) { Matrix E; E.unit(); while(k) { if(k%2) E = Jjcf(E, p); p = Jjcf(p, p); k /= 2; } return E; } Matrix Jjcf(Matrix p1, Matrix p2) { Matrix pe; LL i, j, k; memset(pe.a, 0, sizeof(pe.a)); for(i=1;i<=4;i++) { for(j=1;j<=4;j++) { for(k=1;k<=4;k++) pe.a[i][j] = (pe.a[i][j]+p1.a[i][k]*p2.a[k][j])%mod; } } return pe; }
