H5N1型高致病性禽流感击了bzbz国

H5N1型高致病性禽流感击了bzbz国，不可避免的，bzbz 国的大量鸡死于流感。经过数周的紧急研究，鸡健康组织终于发现，病毒是由两种非常简单的基因组成的，分别示为 101 和 111。很不幸，bzbz国鸡的 DNA 只由 0 和 1 两种组成。假如一只鸡含有病毒两种DNA中的一个，这只鸡就可能被感染。   假如鸡的基因长度为 L，显然，就有 2^L 种基因不同的鸡。问这些鸡中，有多少不会被感染？ 【文件输入】 　一行为DNA的长度 L ( L<=10^9 )。 【文件输出】 　 一行，输出不会被感染的基因个数 Mod 2008 的值。 【样例输入】 4 【样例输出】 9 f[i,k]表示前i个字符末两位为状态k，满足条件的数 k=0表示末尾为‘00’，1表示‘01’，2表示‘10’，3表示‘11’ 基本转移方程： f[i,0]=f[i-1,0]+f[i-1,2] f[i,1]=f[i-1,0] f[i,2]=f[i-1,1]+f[i-1,3] f[i,3]=f[i-1,1] 设表示长度为n的不被感染的基因个数a[n]就满足： a[n]=F[n,0]+F[n,1]+F[n,2]+F[n,3]       ① 对于这道，如果单纯枚举O(n)的算法都要超时。 对于①式展开为： a[n]=2*f[n-1,0]+2*f[n-1,1]+f[n-1,2]+f[n-1,3]        =f[n-1,0]+f[n-1,1]+f[n-1,2]+f[n-1,3]+(f[n-1,0]+f[n-1,1])        =a[n-1]+f[n-1,0]+f[n-1,1] f[n-1,0]+f[n-1,1]=f[n-2,0]+f[n-2,2]+f[n-2,0]    = 2*f[n-3,0]+f[n-3,1]+2*f[n-3,2]+f[n-3,3]        =(f[n-3,0]+f[n-3,1]+f[n-3,2]+f[n-3,3])+(f[n-3,0]+f[n-3,2])        =a[n-3]+(f[n-4,0]+f[n-4,1]+f[n-4,2]+f[n-4,3])        =a[n-3]+a[n-4] 所以可以得到关系： a[n]=a[n-1]+a[n-3]+a[n-4]     这样我们可以很容易计算出a[1]到a[10]的答案:a[1]=2; a[2]=4; a[3]=6; a[4]=9; 这样我们可以很容易计算出a[1]到a[10]的答案:a[1]=2; a[2]=4; a[3]=6; a[4]=9; 很容易想到矩阵乘幂优化k阶常系数线性递推关系：        这样就完成递推，对于需要推多次的，把4*4那个矩阵拿来二分矩阵乘幂，乘得的结果再和初始的1*4那个矩阵乘。 #include #include int b[5][5]={0},c[5][5]={0},a[5][5]={0},t[35]={0},n,i,m,mod; void cheng(int a[][5],int b[][5])//矩阵相乘。 {    int c[5][5]={0},i,j,k;     for(i=1;i<=4;i++)         for(j=1;j<=4;j++)           for( k=1;k<=4;k++)             c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;     memmove(a,c,sizeof(c));//复制数组 int main(int argc, char *argv[]) {scanf("%d",&n); mod=2008;     c[1][1]=2; c[1][2]=4; c[1][3]=6; c[1][4]=9;     if(n<=4)printf("%d",c[1][n]);     else {n-=4;         while(n>0){t[++t[0]]=n%2; n/=2;}         b[1][4]=b[2][1]=b[2][4]=b[3][2]=b[4][3]=b[4][4]=1;         memmove(a,b,sizeof(b));         for( i=t[0]-1;i>=1;i--)         {  cheng(a,a);        //快速取幂。               if(t[i]==1)cheng(a,b); }         cheng(c,a);         printf("%d",c[1][4]);         }    system("PAUSE");      return 0; }