题目描述
考虑递推关系式\(f(n)=a_1*f(n-1)+a_2*f(n-2)+....+a_d*f(n-d)\)，计算\(f(n)\%m\)
输入包含多组测试数据。每组数据第一行为三个整数\(d,n,m(1<=d<=15,1<=n<=2^{31}-1,1<=m<=46340)\)。
第二行包含\(d\)个非负整数\(a_1,a_2.....a_d\)。第三行为\(d\)个非负整数\(f(1),f(2).....f(d)\)。这些数字均不超过\(2^{31}-1\)。输入结束的标志是\(d=n=m=0\).
Output
对于每组数据，输出\(f(n)\%m\)
1 1 100
2
1
2 10 100
1 1
1 1
0 0 0
Sample Output
1
55
非常经典的矩阵优化递推入门题。
由题意得：有初始矩阵\(A_1\)和递推矩阵\(g\)。
\(A_1*g^{i-1}=A_i\)。
一个\(f(n)\)的值只与前\(d\)个的\(f()\)值有关，所以，我们只用构造一个\(d*d\)的矩阵。
\(g\)=\(\begin{pmatrix} a_1 & a_2 & a_3 & \cdots & a_d \\ 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\\vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 0 \\ \end{pmatrix}，\)\(A_1\)=\(\begin{pmatrix} f_d & 0 & 0 & \cdots & 0 \\ f_{d-1} & 0 & 0 & \cdots & 0 \\ f_{d-2} & 0 & 0 & \cdots & 0 \\\vdots & \vdots & \vdots & \ddots & \vdots \\ f_1 & 0 & 0 & \cdots & 0 \\ \end{pmatrix}\)
最后，根据矩阵快速幂求解即可。
空间复杂度\(O(d^2)\)，时间复杂度\(O(d^2*log_n)\)。
代码如下
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
#define LL long long
#define u64 unsigned long long
#define reg register
#define debug(x) cerr<<#x<<" = "<<x<<endl;
#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a)
#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a)
#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a)
#define erep(i,G,x) for(reg int i=(G).Head[x]; i; i=(G).Nxt[i])
inline int Read() {
int res = 0, f = 1;
char c;
while (c = getchar(), c < 48 || c > 57)if (c == '-')f = 0;
do res = (res << 3) + (res << 1) + (c ^ 48);
while (c = getchar(), c >= 48 && c <= 57);
return f ? res : -res;
}
template<class T>inline bool Min(T &a, T const&b) {return a > b ? a = b, 1 : 0;}
template<class T>inline bool Max(T &a, T const&b) {return a < b ? a = b, 1 : 0;}
const int N = 5e5 + 5, M = 25, mod = 1e9 + 9;
struct Matrix {
int Num[M][M];
inline void Init(void) {memset(Num, 0, sizeof Num);}
};
int A[M], d, n, Mod;
Matrix mul(Matrix a, Matrix b) {
Matrix Ans;
Ans.Init();
rep(k, 1, d)rep(i, 1, d)rep(j, 1, d) Ans.Num[i][j] = (Ans.Num[i][j] + (a.Num[i][k] * b.Num[k][j]) % Mod) % Mod;
return Ans;
}
inline void _main(void) {
while (~scanf("%lld %lld %lld", &d, &n, &Mod)) {
if (!d && !n && !Mod)return;
Matrix Ans, us, T;
us.Init(), Ans.Init(), T.Init();
rep(i, 1, d)us.Num[1][i] = Read();
rep(i, 2, d)us.Num[i][i - 1] = 1;
rep(i, 1, d)Ans.Num[d - i + 1][1] = Read();
rep(i, 1, d)T.Num[i][i] = 1;
if (n <= d) {
printf("%lld\n", Ans.Num[d - n + 1][1]);
continue;
}
n = n - d;
while (n) {
if (n & 1)T = mul(T, us);
us = mul(us, us);
n >>= 1;
}
Ans = mul(T, Ans);
printf("%lld\n", Ans.Num[1][1] % Mod);
}
}
signed main() {
#define offline1
#ifdef offline
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
_main();
fclose(stdin); fclose(stdout);
#else
_main();
#endif
return 0;
}
转载于:https://www.cnblogs.com/dsjkafdsaf/p/11309839.html
