UVA10870 Recurrences （矩阵快速幂及构造方法详解）

题意：

　　F（n） = a₁ * F（n-1） + a₂ * F（n-2）+ ···· + a_d * F（n-d）。

　　求给你的n 。很明显这是一道矩阵快速幂的题目。

题解：

　　[F_n-1, F_n-2, F_n-3, ···, F_n-d] * A（矩阵） = [F_n, F_n-1, F_n-2, ···, F_n-d+1] 。

　　F_n = 第一个矩阵 * A的第一列，所以A矩阵的第一列为（a1, a2 , ··· ad）。

　　F_n = 第一个矩阵 * A的第二列，所以A矩阵的第二列为（1， 0， 0，···， 0）。

　　同理可以推出整个A矩阵：

　　a1　　1　　0　　··· 0

　　a2　　0　　1　　··· 0

　　a3　　0　　0　　··· 0

　　···　　0　　0　　···　 1

　　ad　　0　　0　　0　　0

　　当n 小于等于d 的时候直接输出。

　　[ f(d), f(d-1), f(d-2), ···, f(2), f(1) ] * A^n-d = [F_n, F_n-1, F_n-2, ···, F_n-d+1] 。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <vector>
 8 #include <queue>
 9 #include <map>
10 #include <stack>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 #define ms(a, b) memset(a, b, sizeof(a))
15 #define pb push_back
16 #define mp make_pair
17 const LL INF = 0x7fffffff;
18 const int inf = 0x3f3f3f3f;
19 const int maxn = 10+10;
20 int mod;
21 struct Matrix
22 {
23     LL c[maxn][maxn];
24 };//Matrix 矩阵
25 Matrix mult(Matrix a, Matrix b, int len)//矩阵乘法
26 {
27      Matrix hh={0};
28      for(int i=0;i<len;i++)
29         for(int j =0;j<len;j++)
30             for(int k = 0;k<len;k++){
31                 hh.c[i][j] += (a.c[i][k]*b.c[k][j])%mod;
32                 hh.c[i][j] %= mod;
33             }
34     return hh;
35 }
36 Matrix qpow_Matrix(Matrix a, int b, int len)
37 {
38     Matrix base = a;
39     Matrix ans;
40     //初始化ans = 1。
41     for(int i =0;i<len;i++)
42         for(int j =0;j<len;j++)
43             if(i==j)    ans.c[i][j] = 1;
44             else ans.c[i][j] = 0;
45     //
46     while(b){
47         if(b&1)     ans = mult(ans, base, len);
48         base = mult(base, base, len);
49         b>>=1;
50     }
51     return ans;
52 }
53 int a[maxn];
54 int f[maxn];
55 void solve(int d, int n, int m){
56     mod = m;
57     for(int i = 1;i<=d;i++) cin >> a[i];
58     for(int i = 1;i<=d;i++) cin >> f[i];
59 
60     Matrix begin={0};
61     for(int j = 0;j<d;j++){
62         begin.c[0][j] = f[d-j]%mod;
63     }
64     Matrix A={0};
65     for(int j = 0;j<d;j++)
66         A.c[j][0] = a[j+1]%mod;
67     for(int j = 0;j<d;j++){
68         A.c[j][j+1] = 1;
69     }
70     if(n<=d){
71         cout << f[n]%mod << endl;
72         return;
73     }
74     Matrix temp = qpow_Matrix(A, n-d, d);
75     Matrix ans = mult(begin, temp, d);
76     cout << ans.c[0][0]%mod << endl;
77     return;
78 }
79 int main() {
80 #ifdef LOCAL
81     freopen("input.txt", "r", stdin);
82 //        freopen("output.txt", "w", stdout);
83 #endif
84 //    ios::sync_with_stdio(0);
85 //    cin.tie(0);
86     int d, n, m;
87     while(cin >> d >> n >> m){
88         if(d+n+m==0)    break;
89         solve(d, n, m);
90     }
91     return 0;
92 }

View Code