UVA10870 Recurrences —— 矩阵快速幂

题目链接：https://vjudge.net/problem/UVA-10870

题意：

典型的矩阵快速幂的运用。比一般的斐波那契数推导式多了几项而已。

代码如下：

 1 #include <bits/stdc++.h>
 2 #define rep(i,s,t) for(int (i)=(s); (i)<=(t); (i)++)
 3 #define ms(a,b) memset((a),(b),sizeof((a)))
 4 using namespace std;
 5 typedef long long LL;
 6 const int INF = 2e9;
 7 const LL LNF = 9e18;
 8 const double eps = 1e-6;
 9 const int mod = 10000007;
10 const int maxn = 2e5+10;
11 
12 struct MA
13 {
14     LL mat[20][20];
15     void init()
16     {
17         rep(i,1,19) rep(j,1,19)
18             mat[i][j] = (i==j);
19     }
20 };
21 
22 LL n,d,m;
23 LL a[20],f[20];
24 
25 MA mul(MA x, MA y)
26 {
27     MA tmp;
28     ms(tmp.mat,0);
29     rep(i,1,d) rep(j,1,d) rep(k,1,d)
30         tmp.mat[i][j] += (1LL*x.mat[i][k]*y.mat[k][j])%m, tmp.mat[i][j] %= m;
31     return tmp;
32 }
33 
34 MA qpow(MA x, LL y)
35 {
36     MA s;
37     s.init();
38     while(y)
39     {
40         if(y&1) s = mul(s,x);
41         x = mul(x,x);
42         y >>= 1;
43     }
44     return s;
45 }
46 
47 int main()
48 {
49     while(scanf("%lld%lld%lld",&d,&n,&m) && (d || n||m))
50     {
51         rep(i,1,d) scanf("%lld",&a[i]);
52         rep(i,1,d) scanf("%lld",&f[i]);
53 
54         if(n<=d)
55         {
56             printf("%lld
", f[n]);
57             continue;
58         }
59 
60         MA x;
61         ms(x.mat,0);
62         rep(i,1,d) x.mat[1][i] = a[i];
63         rep(i,2,d) x.mat[i][i-1] = 1;
64         x = qpow(x,n-d);
65 
66         LL ans = 0;
67         rep(i,1,d)
68             ans += (1LL*x.mat[1][i]*f[d-i+1])%m, ans %= m;
69         printf("%lld
",ans);
70     }
71 }

View Code