HDU 6470 【矩阵快速幂】

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6470

写这道题是为了让自己不要忘记矩阵快速幂如何推出矩阵式子的。

注意代码是TLE的！！

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define mem(a, b) memset(a, b, sizeof(a))
 4 typedef long long ll;
 5 const int mod = 123456789;
 6 
 7 ll n;
 8 
 9 struct Matrix
10 {
11     ll a[10][10];
12 }A, res, temp;
13 
14 Matrix Multiply(Matrix a, Matrix b)
15 {
16     Matrix ans;
17     mem(ans.a, 0);
18     for(int i = 1; i <= 6; i ++)
19         for(int j = 1; j <= 6; j ++)
20             for(int k = 1; k <= 6; k ++)
21             {
22                 ans.a[i][j] += a.a[i][k] * b.a[k][j] % mod;
23                 ans.a[i][j] %= mod;
24             }
25     return ans;
26 }
27 
28 int main()
29 {
30     mem(A.a, 0);  //构造矩阵 
31     A.a[1][2] = A.a[2][2] = A.a[2][3] = A.a[3][3] = A.a[3][6] = A.a[4][4] = A.a[4][6] = A.a[5][5] = A.a[5][6] = A.a[6][6] = 1;
32     A.a[2][1] = A.a[4][5] = 2;
33     A.a[3][4] = A.a[3][5] = 3;
34     int T;
35     scanf("%d", &T);
36     while(T --)
37     {
38         temp = A;  //初始化temp矩阵 
39         mem(res.a, 0); //初始化为单位矩阵 
40         for(int i = 1; i <= 6; i ++)
41             res.a[i][i] = 1;
42         scanf("%lld", &n);
43         n -= 2;
44         while(n)
45         {
46             if(n % 2)
47                 res = Multiply(res, temp);
48             temp = Multiply(temp, temp);
49             n /= 2;
50         }
51         printf("%lld
", (1 * res.a[2][1] % mod + 2 * res.a[2][2] % mod + 27 * res.a[2][3] % mod + 9 * res.a[2][4] % mod + 3 * res.a[2][5] % mod + res.a[2][6] % mod) % mod);
52     }
53     return 0;
54 }

View Code