HDU 3658：矩陣快速冪計算字符串填充方案數

題目

長度 m 字符串填充字母 'A'-'Z','a'-'z' (52 個)。相鄰字符 ASCII 差 ≤ 32，且至少存在一對差 = 32。求方案數模 1,000,000,007。

補集轉化

總方案（差 ≤ 32） - 方案（差 < 32） = 方案（至少一對差 = 32）。
構造兩個 52×52 轉移矩陣：
• M1[i][j] = 1 若 |i-j| ≤ 32（大寫 0-25，小寫 26-51）
• M2[i][j] = 1 若 |i-j| < 32（即去掉差恰好 32 的大小寫對應對）
初始向量全 1。計算 M^(m-1)，向量和即方案數。答案 = (sum(M1) - sum(M2)) % MOD。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
struct Mat { long long a[52][52]; };
Mat mul(Mat x, Mat y) {
    Mat r; memset(r.a,0,sizeof(r.a));
    for(int i=0;i<52;i++) for(int k=0;k<52;k++) if(x.a[i][k])
        for(int j=0;j<52;j++) r.a[i][j]=(r.a[i][j]+x.a[i][k]*y.a[k][j])%MOD;
    return r;
}
Mat power(Mat base, long long exp) {
    Mat res; memset(res.a,0,sizeof(res.a));
    for(int i=0;i<52;i++) res.a[i][i]=1;
    while(exp){ if(exp&1) res=mul(res,base); base=mul(base,base); exp>>=1; }
    return res;
}
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        long long m; scanf("%lld", &m);
        Mat M1={}, M2={};
        // 大寫 0-25, 小寫 26-51
        for(int i=0;i<26;i++) {
            for(int j=0;j<=i+26;j++) M1.a[j][i]=M2.a[j][i]=1;
            M2.a[i+26][i]=0; // 去掉大寫->對應小寫 (差32)
        }
        for(int i=26;i<52;i++) {
            for(int j=i-26;j<52;j++) M1.a[j][i]=M2.a[j][i]=1;
            M2.a[i-26][i]=0; // 去掉小寫->對應大寫
        }
        Mat R1 = power(M1, m-1), R2 = power(M2, m-1);
        long long s1=0, s2=0;
        for(int i=0;i<52;i++) { s1=(s1+R1.a[0][i])%MOD; s2=(s2+R2.a[0][i])%MOD; }
        printf("%lld\n", (s1 - s2 + MOD) % MOD);
    }
    return 0;
}