P10503 - 233 Matrix 题解

1
#include <bits/stdc++.h>
2
#define N 15
3
#define MOD 10000007
4
using namespace std;
5

6
typedef long long ll;
7
typedef pair<int, int> PII;
8

9
int n, m;
10
struct Matrix {
11
    ll mat[N][N]{};
12

13
    Matrix() {
14
        memset(mat, 0, sizeof mat);
15
    }
16

17
    void I() {
18
        for (int i = 1; i <= n + 2; i++) mat[i][i] = 1;
19
    }
20
};
21

22
Matrix operator*(const Matrix &l, const Matrix &r) {
23
    Matrix res;
24
    for (int i = 1; i <= n + 2; i++) {
25
        for (int j = 1; j <= n + 2; j++) {
26
            for (int k = 1; k <= n + 2; k++) {
27
                res.mat[i][j] = (res.mat[i][j] + l.mat[i][k] % MOD * r.mat[k][j] % MOD) % MOD;
28
            }
29
        }
30
    }
31
    return res;
32
}
33

34
Matrix qpow(Matrix a, ll b) {
35
    Matrix res;
36
    res.I();
37
    while (b) {
38
        if (b & 1) res = res * a;
39
        a = a * a;
40
        b >>= 1;
41
    }
42
    return res;
43
}
44

45
void print(Matrix m) {
46
    for (int i = 1; i <= n + 2; i++) {
47
        for (int j = 1; j <= n + 2; j++) {
48
            cout << setw(5) << m.mat[i][j] << ' ';
49
        }
50
        cout << endl;
51
    }
52
}
53

54
int main() {
55
    ios::sync_with_stdio(false);
56
    cin.tie(nullptr);
57
    cout.tie(nullptr);
58

59
    while (cin >> n >> m) {
60
        Matrix A, M;
61
        A.mat[1][1] = 1, A.mat[1][2] = 23;
62
        for (int i = 1; i <= n; i++) {
63
            int x;
64
            cin >> x;
65
            A.mat[1][i + 2] = x;
66
        }
67
        for (int i = 1; i <= n + 2; i++) {
68
            for (int j = i; j <= n + 2; j++) {
69
                M.mat[i][j] = 1;
70
            }
71
        }
72
        for (int i = 2; i <= n + 2; i++) M.mat[1][i] = 3, M.mat[2][i] = 10;
73
        A = A * qpow(M, m);
74
        cout << A.mat[1][n + 2] % MOD << endl;
75
    }
76
    return 0;
77
}