BNU 34895 Elegant String：矩陣快速冪解決字串計數

問題大意

長度為 n 的序列，元素取自 0~k。求不包含 0~k 全排列的子串個數。結果模 20140518。

動態規劃與狀態轉移

定義 dp[i][j] 為前 i 位、當前有 j 個相同元素的方案數。寫出遞推關係，構造轉移矩陣，利用矩陣快速冪加速。

矩陣構造

• 狀態數 k+1（0~k 個連續相同）。
• 轉移矩陣 mat 大小 k x k，根據遞推式填充。
• 初始向量對應長度 1 時的狀態。

完整代碼

#include <cstdio>
#include <cstring>
typedef long long ll;
const ll MOD = 20140518;
const int N = 20;

struct mat { int r, c; ll s[N][N];
    void init(int k, int sign) {
        memset(s, 0, sizeof(s));
        if (sign) { // 轉移矩陣
            r = c = k;
            for (int i = 1; i <= r; i++) {
                for (int j = i; j <= r; j++) s[i][j] = 1;
                if (i == r) continue;
                s[i+1][i] = k+1-i;
            }
        } else { // 初始向量
            r = k; c = 1; s[1][1] = k+1;
        }
    }
};

mat mul(mat a, mat b) {
    mat ans; memset(ans.s, 0, sizeof(ans.s));
    for (int i = 1; i <= a.r; i++)
        for (int j = 1; j <= b.c; j++)
            for (int x = 1; x <= a.c; x++)
                ans.s[i][j] = (ans.s[i][j] + a.s[i][x] * b.s[x][j]) % MOD;
    ans.r = a.r; ans.c = b.c; return ans;
}

ll n; int k;
ll solve(ll x) {
    if (x == 1) return k+1;
    x--;
    mat ans, cur; ans.init(k, 0); cur.init(k, 1);
    while (x) {
        if (x & 1) ans = mul(cur, ans);
        cur = mul(cur, cur);
        x >>= 1;
    }
    int sum = 0;
    for (int i = 1; i <= k; i++) sum = (sum + ans.s[i][1]) % MOD;
    return sum;
}

int main() {
    int cas; scanf("%d", &cas);
    for (int i = 1; i <= cas; i++) {
        scanf("%lld%d", &n, &k);
        printf("Case #%d: %lld\n", i, solve(n));
    }
    return 0;
}