DecodingGenome(CodeForces-222E)【矩阵快速幂】

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 long long n;
 5 const int mo=1e9+7;
 6 int m,k;
 7 long long num[60];
 8 long long restrict[60][60];
 9 char tm1,tm2;
10 
11 int pow(long long x){
12     x--;
13     long long res[60][60],ttp[60][60]={0};
14     for(int i=1;i<=m;i++)
15         res[i][i]=1;
16     while(x!=0){
17         if(x&1){
18             memset(ttp,0,sizeof(ttp));
19             for(int ii=1;ii<=m;ii++){
20             for(int i=1;i<=m;i++){
21                 for(int j=1;j<=m;j++){
22                     ttp[ii][j]+=res[ii][i]*restrict[i][j]%mo;
23                     ttp[ii][j]%=mo;
24                 }
25             }
26             }
27             for(int i=1;i<=m;i++)
28                 for(int j=1;j<=m;j++)
29                     res[i][j]=ttp[i][j];
30         }
31         x>>=1;
32         memset(ttp,0,sizeof(ttp));
33         for(int ii=1;ii<=m;ii++){
34             for(int i=1;i<=m;i++){
35                 for(int j=1;j<=m;j++){
36                     ttp[ii][j]+=restrict[ii][i]*restrict[i][j]%mo;
37                     ttp[ii][j]%=mo;
38                 }
39             }
40         }
41         for(int i=1;i<=m;i++)
42             for(int j=1;j<=m;j++)
43                 restrict[i][j]=ttp[i][j];
44     }
45     long long ans=0;
46     for(int i=1;i<=m;i++){
47         for(int j=1;j<=m;j++){
48             ans+=num[i]*res[i][j]%mo;
49             ans%=mo;
50         }
51     }
52     return ans;
53 }
54 int main(){
55     scanf("%I64d%d%d",&n,&m,&k);
56     for(int i=1;i<=m;i++){
57         for(int j=1;j<=m;j++)
58             restrict[i][j]=1;
59         num[i]=1;
60     }
61     for(int i=1;i<=k;i++){
62         scanf("\n%c%c",&tm1,&tm2);
63        //printf("%c %c\n",tm1,tm2);
64         int x1=tm1>‘Z‘?tm1-‘a‘+1:tm1-‘A‘+27;
65         int x2=tm2>‘Z‘?tm2-‘a‘+1:tm2-‘A‘+27;
66         //printf("%d %d\n",x1,x2);
67         restrict[x1][x2]=0;
68     }
69     printf("%d",pow(n));
70     return 0;
71 }