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

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

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

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;
}