http://acm.hdu.edu.cn/showproblem.php?pid=6185
1
2
1
5
有地毯为2 * 1。有操场4 * n，地毯尽可以横放及竖放，求地毯不重叠的铺满整个地板有多少种方法。
多少种方法其实可以联想到dp，每一个n也刚好可以对应一种状态，但是考虑n的数据范围有点大，dp时间复杂度过高，并不靠谱。实际上通过n的数据范围可以考虑这道题应该是求递推公式的类型。并且稍加思考也确实不难发现规模n与规模n - 1与规模n - 2……确实有着某种关系在里边。因此得出该题应该先求出递推式，然后通过矩阵快速幂的方法得到所需的解。
经过漫长的递推式求解过程，可以得到如下关系式f(x) = 5 * sum(x - 2) + f(x - 3)，于是将代码敲出。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#define ll long long
using namespace std;
const ll MOD = 1e9 + 7;
struct Mat{
ll m[4][4];
}unit;
void Unit(){
for(ll i = 0;i < 4;i++)
unit.m[i][i] = 1;
return;
}
Mat Mult(Mat a,Mat b){
Mat ret;
ll x;
for(ll i = 0;i < 4;i++){
for(ll j = 0;j < 4;j++){
x = 0;
for(ll k = 0;k < 4;k++)
x = (x + a.m[i][k] * b.m[k][j] % MOD) % MOD;
ret.m[i][j] = x;
}
}
return ret;
}
Mat QPow(Mat a,ll n){
Mat ret = unit;
while(n){
if(n & 1) ret = Mult(ret, a);
a = Mult(a, a);
n >>= 1;
}
return ret;
}
int main(){
ll n;
Unit();
while(~scanf("%lld", &n)) {
if(n == 1) printf("1\n");
else if(n == 2) printf("5\n");
else if(n == 3) printf("11\n");
else{
Mat b;
b.m[0][0]=0,b.m[0][1]=1,b.m[0][2]=1,b.m[0][3]=0;
b.m[1][0]=5,b.m[1][1]=1,b.m[1][2]=0,b.m[1][3]=0;
b.m[2][0]=0,b.m[2][1]=0,b.m[2][2]=0,b.m[2][3]=1;
b.m[3][0]=1,b.m[3][1]=0,b.m[3][2]=0,b.m[3][3]=0;
b = QPow(b,n-3);
printf("%lld\n",(11 * b.m[0][0] + 7 * b.m[1][0] + 5 * b.m[2][0] + b.m[3][0]) % MOD);
//11 7 5 1 表示i - 1, sum(i - 2), i - 2, i - 3;
}
}
return 0;
}
原文：https://www.cnblogs.com/TanJI-life/p/14742966.html