【UVA-10870】Recurrences【矩阵快速幂】

【UVA-10870】Recurrences【矩阵快速幂】

Solution:

```#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
int MOD = 0;
const int LIM = 20;
struct Matrix {
LL v[LIM][LIM];
int size;
Matrix operator * (const Matrix & m) const {
Matrix ret = {0};
ret.size = size;
for (int i = 0; i < size; i++) {
for (int k = 0; k < size; k++) {
if (v[i][k])
for (int j = 0; j < size; j++) {
ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
}
}
}
return ret;
}
};

Matrix fastPow(int p, Matrix m) {
Matrix ret = {0};
ret.size = m.size;
for(int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
while (p) {
if (p & 1) ret = ret * m;
m = m * m;
p >>= 1;
}
return ret;
}

LL input[LIM], output[LIM];
Matrix base;

int main() {
int d, n;
while (~scanf("%d%d%d", &d, &n, &MOD) && (d || n) && MOD) {
memset(&base, 0, sizeof base);
base.size = d;
for (int i = 0; i < d; i++)
scanf("%lld", &base.v[0][i]), base.v[0][i] %= MOD;
for (int i = 1; i < d; i++)
base.v[i][i - 1] = 1;
for (int i = 0; i < d; i++)
scanf("%lld", &input[d - 1 - i]), input[d - 1 - i] %= MOD;
if (n <= d) printf("%lld\n", input[d - n]);
else {
base = fastPow(n - d, base);
LL ans = 0;
for (int i = 0; i < d; i++) {
ans = (ans + base.v[0][i] * input[i]) % MOD;
}
printf("%lld\n", ans);
}
}
return 0;
}
```