Happy Necklace (矩阵快速幂 + 递推 + 取模)

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 struct matrix{
 6     long long int mat[4][4];
 7 }A,B;
 8 matrix mul(matrix a,matrix b){
 9     matrix tmp;
10     memset(tmp.mat,0,sizeof(tmp.mat));
11     for(int i = 0;i < 4;i++)
12         for(int j = 0;j < 4;j++)
13             for(int k = 0;k < 4;k++){
14                 tmp.mat[i][j] += a.mat[i][k] * b.mat[k][j];
15                 tmp.mat[i][j] %= 1000000007;
16         }
17     return tmp;
18 }
19 matrix pow_mat(matrix a,long long int n){ //注意n 是long long int 类型,老写成int 类型
20     matrix ans;
21     int num = 0;
22     memset(ans.mat,0,sizeof(ans.mat));
23     for(int i = 0;i < 4;i++)
24         ans.mat[i][i] = 1;
25     while(n){
26         if(n & 1)
27             ans = mul(ans,a);
28         a = mul(a,a);
29         n >>= 1;
30     }
31     return ans;
32 }
33 int main(){
34     long long int t,n;
35     scanf("%lld",&t);
36     while(t--){
37         scanf("%lld",&n);
38         if(n == 2){
39             printf("3\n");
40             continue;
41         }
42         else if(n == 3){
43             printf("4\n");
44             continue;
45         }
46         else if(n == 4){
47             printf("6\n");
48             continue;
49         }
50         else if(n == 5){
51             printf("9\n");
52             continue;
53         }
54         else{
55             A.mat[0][0] = 3,A.mat[0][1] = 4,A.mat[0][2] = 6,A.mat[0][3] = 9;
56             B.mat[0][0] = 0,B.mat[0][1] = 0,B.mat[0][2] = 1,B.mat[0][3] = 0;
57             B.mat[1][0] = 1,B.mat[1][1] = 0,B.mat[1][2] = 0,B.mat[1][3] = 1;
58             B.mat[2][0] = 0,B.mat[2][1] = 1,B.mat[2][2] = 1,B.mat[2][3] = 0;
59             B.mat[3][0] = 0,B.mat[3][1] = 0,B.mat[3][2] = 0,B.mat[3][3] = 1;
60             B = pow_mat(B,n - 5);
61             printf("%lld\n",mul(A,B).mat[0][3]);
62         }
63     }
64     return 0;
65 }