题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6185
题意：用 1 * 2 的小长方形完全覆盖 4 * n的矩形有多少方案。
解法：小范围是一个经典题，之前写过，见这里：http://blog.csdn.net/just_sort/article/details/73650284
然后推出前几项发现是有规律的，要问如何发现规律，不妨丢到std跑一跑。。。
#include<bits/stdc++.h>
using namespace std;
#define ld double
const int SZ=1e5;
int n;
typedef vector<ld> vld;
vld ps[2333];
int pn=0,fail[SZ];
ld x[SZ],delta[SZ];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf",x+i);
for(int i=1;i<=n;i++)
{
ld dt=-x[i];
for(int j=0;j<ps[pn].size();j++)
dt+=x[i-j-1]*ps[pn][j];
delta[i]=dt;
if(fabs(dt)<=1e-7) continue;
fail[pn]=i; if(!pn) {ps[++pn].resize(1); continue;}
vld&ls=ps[pn-1]; ld k=-dt/delta[fail[pn-1]];
vld cur; cur.resize(i-fail[pn-1]-1); //trailing 0
cur.push_back(-k); for(int j=0;j<ls.size();j++) cur.push_back(ls[j]*k);
if(cur.size()<ps[pn].size()) cur.resize(ps[pn].size());
for(int j=0;j<ps[pn].size();j++) cur[j]+=ps[pn][j];
ps[++pn]=cur;
}
for(unsigned g=0;g<ps[pn].size();g++)
printf("%f ",ps[pn][g]);
return 0;
}
发现规律是dp[i] = dp[i-1] + 5*dp[i-2] + dp[i-3] - dp[i-4]。然后就是简单的矩阵快速幂。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
struct Matrix{
LL a[4][4];
void set1(){
memset(a,0,sizeof(a));
}
void set2(){
memset(a, 0, sizeof(a));
for(int i=0; i<4; i++){
a[i][i]=1;
}
}
};
Matrix operator * (const Matrix &a, const Matrix &b){
Matrix res;
res.set1();
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
for(int k=0; k<4; k++){
res.a[i][j] = (res.a[i][j]+a.a[i][k]*b.a[k][j]+mod)%mod;
}
}
}
return res;
}
Matrix qsm(Matrix a, LL n){
Matrix res;
res.set2();
while(n){
if(n&1) res=res*a;
a = a*a;
n>>=1;
}
return res;
}
LL n;
int main()
{
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{
Matrix a,b;
a.a[0][0] = 1, a.a[0][1] = 5, a.a[0][2] = 1, a.a[0][3] = -1;
a.a[1][0] = 1, a.a[1][1] = 0, a.a[1][2] = 0, a.a[1][3] = 0;
a.a[2][0] = 0, a.a[2][1] = 1, a.a[2][2] = 0, a.a[2][3] = 0;
a.a[3][0] = 0, a.a[3][1] = 0, a.a[3][2] = 1, a.a[3][3] = 0;
b.set1();
b.a[0][0] = 36;
b.a[1][0] = 11;
b.a[2][0] = 5;
b.a[3][0] = 1;
a = qsm(a, n-4);
a = a*b;
printf("%lld\n", a.a[0][0]%mod);
}
}
return 0;
}