http://acm.pku.edu.cn/JudgeOnline/problem?id=2440這是一個(gè)遞推的題目，公式的推導(dǎo)過(guò)程如下：
合法的情況：
000 001 010 011 100 110
設(shè)達(dá)到長(zhǎng)度n-1的時(shí)候，得到的分別以上述串結(jié)尾的序列個(gè)數(shù)分別為
f1(n-1) f2(n-1) f3(n-1) f4(n-1) f5(n-1) f6(n-1)
則總共的序列個(gè)數(shù)F(n-1)＝f1(n-1)+f2(n-1)+f3(n-1)+f4(n-1)+f5(n-1)+f6(n-1)
則:
f1(n)=f1(n-1)+f5(n-1)
f2(n)=f1(n-1)+f5(n-1)
f3(n)=f2(n-1)
f4(n)=f2(n-1)
f5(n)=f3(n-1)+f6(n-1)
f6(n)=f4(n-1)
F(n)=f1(n)+f2(n)+f3(n)+f4(n)+f5(n)+f6(n)
=f1(n-1)+f5(n-1)+f1(n-1)+f5(n-1)+f2(n-1)+f2(n-1)+f3(n-1)+f6(n-1)+f4(n-1)
=F(n-1)+f1(n-1)+f2(n-1)+f5(n-1)
=F(n-1)+f1(n-2)+f5(n-2)+f1(n-2)+f5(n-2)+f3(n-2)+f6(n-2)
=F(n-1)+2*f1(n-2)+2*f5(n-2)+f3(n-2)+f6(n-2)
=F(n-1)+2*f1(n-3)+2*f5(n-3)+2*f3(n-3)+2*f6(n-3)+f2(n-3)+f4(n-3)
=F(n-1)+F(n-3)+f1(n-3)+f3(n-3)+f5(n-3)+f6(n-3)
=F(n-1)+F(n-3)+f1(n-4)+f5(n-4)+f2(n-4)+f3(n-4)+f6(n-4)+f4(n-4)
=F(n-1)+F(n-3)+F(n-4)
由于是求對(duì)2005的模，因此很容易想到肯定有循環(huán)出現(xiàn)。經(jīng)計(jì)算循環(huán)是200。但是，我下面用矩陣求解。
根據(jù)遞推式構(gòu)造矩陣的方法是：
設(shè)遞推式是：f(n) =a1*f(n-1)+a2*f(n-2)+a3*f(n-3)
又有：f(n-1)= f(n-1)
和：f(n-2)= f(n-2)
然后就有
f(n) a1 a2 a3 f(n-1)
f(n-1) 1 0 0 f(n-2)
f(n-2) 0 1 0 f(n-3)
因此矩陣就是 a1 a2 a3
1 0 0
0 1 0
對(duì)于該題而言，矩陣A是 1 0 1 1
1 0 0 0
0 0 0 0
0 1 0 0
0 0 1 0
F(n)=A*F(n-1)
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
void copy(int sor[][4],int des[][4])
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
des[i][j]=sor[i][j];
}
void mul(int sor1[][4],int sor2[][4],int des[][4])
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
des[i][j]=0;
for(int k=0;k<4;k++)
{
des[i][j]=(des[i][j]+sor1[i][k]*sor2[k][j])%2005;
}
}
}
void multiply(int mat[][4],int l,int res[][4])
{
if(l<=0)
{
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
res[i][j]=0;
res[i][i]=1;
}
}
else if(l==1)
{
copy(mat,res);
}
else
{
int tmp[4][4];
multiply(mat,l/2,res);
mul(res,res,tmp);
if(l%2)
mul(tmp,mat,res); // res = tmp * mat
else copy(tmp,res); //tmp copy-> res;
}
}
void multiply2(int res[][4],int b[],int ans[])
{
for(int i=0;i<4;i++)
{
ans[i]=0;
for(int j=0;j<4;j++)
ans[i]=(ans[i]+res[i][j]*b[j])%2005;
}
}
int solve(int l)
{
int f[]={1,2,4,6};
if(l<4)
return f[l];
int mat[4][4]={{1,0,1,1},{1,0,0,0},{0,1,0,0},{0,0,1,0}};
int b[]={6,4,2,1};
int res[4][4],ans[4];
multiply(mat,l-3,res); //res = mat^l
multiply2(res,b,ans); // ans=res*b
return ans[0];
}
int main()
{
int l;
while(scanf("%d",&l)!=EOF)
{
printf("%d\n",solve(l));
}
}