ZOJ 3538 Arrange the Schedule：矩陣快速冪解決分段排程計數

題目大意

n 天訓練，每天由 4 個小組（A,B,C,D）輪流出題。限制：
1. 同一小組不能連續兩天出題。
2. m 天已指定小組（不可更改）。
求合法排程數對 1e9+7 取模。n ≤ 1e7，m ≤ 10。

矩陣建模

狀態：當天出題小組（4 種）。轉移矩陣 T 為 4×4，T[i][j] = 1 若 i ≠ j，否則 0。
若第 k 天固定為小組 c，則該天轉移矩陣 T_fixed 僅第 c 行保留原值，其餘行全 0（即強制轉移到 c）。

分段快速冪

將 n 天按固定日子分段。假設固定日子為 d₁, d₂, ..., dₘ。
- 第 1 天到 d₁-1：自由轉移，矩陣 T。
- 第 d₁ 天：固定矩陣 T_fixed(d₁)。
- 第 d₁+1 到 d₂-1：自由轉移 T。
- 以此類推，最後一段到第 n 天。
初始向量 v = [1,1,1,1]（第 1 天可任意小組，若第 1 天固定則對應位置為 1 其餘 0）。
答案 = v × (矩陣乘積) × [1,1,1,1]ᵀ。

矩陣乘法順序注意

若向量為行向量左乘，矩陣乘積順序為 M₁ × M₂ × ... 對應時間順序。代碼中需確保乘法順序正確（先算左側矩陣）。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;

struct Matrix {
    long long a[4][4];
    Matrix(bool ident = false) { memset(a, 0, sizeof(a)); if (ident) for (int i=0;i<4;++i) a[i][i]=1; }
};

Matrix mul(const Matrix& A, const Matrix& B) {
    Matrix C;
    for (int i=0;i<4;++i)
        for (int k=0;k<4;++k) if (A.a[i][k])
            for (int j=0;j<4;++j)
                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD;
    return C;
}

Matrix mpow(Matrix base, long long exp) {
    Matrix res(true);
    while (exp) {
        if (exp & 1) res = mul(base, res); // 注意順序：base * res
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n; int m;
    while (cin >> n >> m) {
        vector> fix(m);
        for (int i=0;i> fix[i].first >> fix[i].second;
        sort(fix.begin(), fix.end());

        Matrix T; // 自由轉移矩陣
        for (int i=0;i<4;++i) for (int j=0;j<4;++j) if (i!=j) T.a[i][j]=1;

        Matrix ans(true); // 初始為單位矩陣
        long long cur = 1;
        long long init[4] = {1,1,1,1};

        if (m > 0 && fix[0].first == 1) {
            fill(init, init+4, 0);
            init[fix[0].second - 'A'] = 1;
            cur = 1;
        }

        for (int i=0;i cur) {
                Matrix seg = mpow(T, day - cur);
                ans = mul(seg, ans);
            }
            // 固定日子矩陣
            Matrix fixMat;
            int c = fix[i].second - 'A';
            for (int j=0;j<4;++j) if (j != c) fixMat.a[c][j] = 1;
            ans = mul(fixMat, ans);
            cur = day + 1;
        }
        if (cur <= n) {
            Matrix seg = mpow(T, n - cur + 1);
            ans = mul(seg, ans);
        }

        long long res = 0;
        for (int i=0;i<4;++i)
            for (int j=0;j<4;++j)
                res = (res + ans.a[i][j] * init[j]) % MOD;
        cout << res << '\n';
    }
    return 0;
}

複雜度

矩陣乘法 O(4³)，快速冪 O(log n)，最多 m+1 ≤ 11 段，總時間 O(m · 4³ log n)，極快。