HDU 3658 矩陣快速冪解題詳解：字母序列排列計數

題目大意

給定序列長度 n，序列由大小寫字母（A-Z, a-z，共 52 個字元）組成。相鄰字母的 ASCII 碼差值必須 ≤ 32，且序列中至少要有一組相鄰字母差值恰好等於 32。求合法序列總數模 1,000,000,007。

核心思路：矩陣快速冪 + 容斥原理

1. 建立狀態轉移矩陣：構造 52×52 矩陣 M，M[i][j] = 1 表示字母 i 後可接字母 j（滿足 |ASCII差| ≤ 32）。
2. 總方案數：計算 M^n-1 的首行元素和，即長度為 n 且滿足「差值 ≤ 32」的所有序列數（記為 Total）。
3. 排除「無差值等於 32」的方案：將矩陣中差值恰好為 32 的轉移（即大小寫同字母互轉：A↔a, B↔b...）設為 0，重新計算矩陣冪得 No32。
4. 答案：(Total - No32 + MOD) % MOD。

矩陣構建邏輯詳解

將 52 個字母編碼 0~25 對應 A-Z，26~51 對應 a-z。

• 大寫字母 (0~25)：後可接 ASCII 碼相差 ≤ 32 的字母。對於 'A'(0)，可接 'A'~'Z'(0~25) 及 'a'(26)；對於 'Z'(25)，可接 'A'~'Z' 及 'z'(51)。
• 小寫字母 (26~51)：同理對稱。對於 'a'(26)，可接 'A'(0) 及 'a'~'z'(26~51)；對於 'z'(51)，可接 'Z'(25) 及 'a'~'z'。
• 程式碼中以兩段迴圈分別處理上半部（大寫行）與下半部（小寫行）的合法轉移。

完整優化程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int SZ = 52;
const int64 MOD = 1'000'000'007LL;

struct Matrix {
    int64 a[SZ][SZ];
    Matrix(bool ident = false) { memset(a, 0, sizeof(a)); if (ident) for (int i=0;i>= 1;
    }
    return res;
}

Matrix buildBase(bool allowDiff32) {
    Matrix M;
    // 大寫字母 0-25
    for (int i=0;i<26;++i) {
        for (int j=0;j<=i+26;++j) M.a[j][i] = 1; // 修正：原碼邏輯為列為起點，行為終點，此處按原意填充
    }
    // 小寫字母 26-51
    for (int i=26;i<52;++i) {
        for (int j=51;j>=i-26;--j) M.a[j][i] = 1;
    }
    // 移除差值恰好為 32 的轉移 (大小寫同字母互轉)
    if (!allowDiff32) {
        for (int i=0;i<26;++i) {
            M.a[i+26][i] = 0; // 大寫 -> 對應小寫
            M.a[i][i+26] = 0; // 小寫 -> 對應大寫
        }
    }
    return M;
}

int64 solve(long long n, bool allowDiff32) {
    if (n == 1) return 52; // 長度1無相鄰限制
    Matrix base = buildBase(allowDiff32);
    Matrix res = mpow(base, n - 1);
    int64 ans = 0;
    for (int i=0;i> T;
    while (T--) {
        long long n; cin >> n;
        int64 total = solve(n, true);
        int64 no32 = solve(n, false);
        cout << (total - no32 + MOD) % MOD << '\n';
    }
    return 0;
}

複雜度分析

• 矩陣乘法：O(52³) ≈ 14 萬次運算。
• 快速冪：O(log n) 次矩陣乘法。
• 單測資總複雜度：O(52³ log n)，極易在時限內通過。

常見坑點提醒

1. 矩陣乘法順序：原碼 res = mul(res, ori) 代表向量乘在左側，需確保矩陣定義一致（行為 From，列為 To，或相反）。
2. 初始向量：原碼 res.g[0][i] = 1 視為長度 1 時以各字母結尾的方案數為 1，故最終求首行和。
3. 模運算：中間乘積可能超過 64 位，C++ long long 夠用（52 × MOD² < 2⁶³），但建議乘法後立即取模。