哈理工 oj 1375The Active Leyni

链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1375

这是一道矩阵乘法的题，要用到快速矩阵乘法，假设f[i][0]表示第i步到s的种类数，f[i][1]表示到a点的种类数，以此类推f[i][0]=f[i-1][1]+f[i-1][2]+f[i-1][3]……………………

数据量很大显然不能用纯粹的递推，递推一般数据较大时都是矩阵乘法，这道题的初始矩阵是[1,0,0,0]即第0步到各个点的走法要乘的矩阵为一个只有对角线全为0，其他皆为1的矩阵

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define mod 1000000007
 4 long long a[32][4][4];//用32位的整型可以表示10^9
 5 long long res[4][4];
 6 void mul(long long m)
 7 {
 8     long long i,j,k;
 9     for(i=0;i<4;i++)
10     for(j=0;j<4;j++)
11     for(k=0;k<4;k++)
12     {
13         a[m][i][j]+=(a[m-1][i][k]*a[m-1][k][j])%mod;
14         a[m][i][j]%=mod;
15     }
16 }
17 void mul2(long long m)
18 {
19     long long temp[4][4];
20     long long i,j,k;
21     memset(temp,0,sizeof(temp));
22     for(i=0;i<4;i++)
23     for(j=0;j<4;j++)
24     for(k=0;k<4;k++)
25     {
26         temp[i][j]+=(res[i][k]*a[m][k][j])%mod;
27         temp[i][j]%=mod;
28     }
29     for(i=0;i<4;i++)
30     for(j=0;j<4;j++)
31     res[i][j]=temp[i][j];
32 }
33 void init()//初始化矩阵a
34 {
35     memset(a,0,sizeof(a));
36     long long i,j;
37     for(i=0;i<4;i++)
38     for(j=0;j<4;j++)
39     {if(i==j)
40     continue;
41     else
42     a[0][i][j]=1;
43     }
44     for(i=1;i<32;i++)
45     mul(i);
46 }
47 int main()
48 {
49     init();
50     long long t;
51     scanf("%lld",&t);
52     long long n,i,j;
53     while(t--)
54     {
55         scanf("%lld",&n);
56         if(n==0)
57         {
58             printf("1\n");
59             continue;
60         }
61         memset(res,0,sizeof(res));
62         for(i=0;i<4;i++)
63         res[i][i]=1;
64         for(i=1,j=0;i<=n;i<<=1,j++)
65         {
66             if(i&n)
67             mul2(j);
68         }
69         printf("%lld\n",res[0][0]);
70     }
71     return 0;
72 }