洛谷P5789 [TJOI2017]可樂（資料加強版） 題解 矩陣快速幂

題目連結：​​https://www.luogu.com.cn/problem/P5789​​

我的了解：矩陣快速幂主要是為了優化狀态轉移。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 2017;
int n, m, t, ans;
struct Matrix {
    int a[101][101];
    Matrix operator * (Matrix b) const {
        Matrix c;
        memset(c.a, 0, sizeof(c.a));
        for (int i = 0; i <= n; i ++)
            for (int j = 0; j <= n; j ++)
                for (int k = 0; k <= n; k ++)
                    c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j]) % MOD;
        return c;
    }
} g, c;
int main() {
    cin >> n >> m;
    memset(g.a, 0, sizeof(g.a));
    for (int i = 0; i <= n; i ++) g.a[i][i] = g.a[i][0] = 1;
    while (m --) {
        int x, y;
        cin >> x >> y;
        g.a[x][y] = g.a[y][x] = 1;
    }
    cin >> t;
    memset(c.a, 0, sizeof(c.a));
    for (int i = 1; i <= n; i ++) c.a[i][i] = 1;
    while (t > 0) {
        if (t % 2) c = c * g;
        g = g * g;
        t /= 2;
    }
    for (int i = 0; i <= n; i ++) ans = (ans + c.a[1][i]) % MOD;
    cout << ans << endl;
    return 0;
}