HDOJ 5411 CRB and Puzzle：矩陣快速冪計數拼圖模式

矩陣快速冪

struct Matrix {
    int a[55][55];
    Matrix operator*(const Matrix &o) const {
        Matrix r; memset(r.a, 0, sizeof(r.a));
        for (int i = 0; i < n; ++i)
            for (int k = 0; k < n; ++k) if (a[i][k])
                for (int j = 0; j < n; ++j)
                    r.a[i][j] = (r.a[i][j] + a[i][k] * o.a[k][j]) % MOD;
        return r;
    }
};
Matrix qpow(Matrix base, long long exp) {
    Matrix res; // 單位矩陣
    for (int i = 0; i < n; ++i) res.a[i][i] = 1;
    while (exp) {
        if (exp & 1) res = res * base;
        base = base * base;
        exp >>= 1;
    }
    return res;
}

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MOD = 2015, MAXN = 55;
int n; long long m;
struct Matrix {
    int a[MAXN][MAXN];
    Matrix() { memset(a, 0, sizeof(a)); }
    void identity() { for (int i = 0; i < n; ++i) a[i][i] = 1; }
    Matrix operator*(const Matrix &o) const {
        Matrix r;
        for (int i = 0; i < n; ++i)
            for (int k = 0; k < n; ++k) if (a[i][k])
                for (int j = 0; j < n; ++j)
                    r.a[i][j] = (r.a[i][j] + a[i][k] * o.a[k][j]) % MOD;
        return r;
    }
};
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%lld", &n, &m);
        Matrix A;
        for (int i = 0; i < n; ++i) {
            int k, x; scanf("%d", &k);
            while (k--) { scanf("%d", &x); A.a[i][x - 1] = 1; }
        }
        // 增廣矩陣 B: size n+1
        Matrix B; int sz = n + 1;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) B.a[i][j] = A.a[i][j];
        for (int j = 0; j < n; ++j) B.a[n][j] = 1; // 最後一行全 1
        B.a[n][n] = 1; // 保持累加
        Matrix ans = qpow(B, m);
        int sum = 0;
        for (int j = 0; j <= n; ++j) sum = (sum + ans.a[n][j]) % MOD;
        printf("%d\n", sum);
    }
    return 0;
}

複雜度

矩陣乘法 O(N³)，冪指數 M ≤ 10⁵，log M ≈ 17，N ≤ 50，總運算量約 50³ × 17 ≈ 2×10⁶，極快。