HDU 2294 Pendant：DP + 矩陣快速冪降維求珍珠首飾方案數

HDU 2294 Pendant：DP + 矩陣快速冪降維求珍珠首飾方案數

有 K 種珍珠，每種 N 顆（N ≤ 1e9），製作長度 [1, N] 的首飾，每種至少用 1 顆。求方案數模 1234567891。

DP 狀態定義

dp[i][j]：長度為 i、使用 j 種珍珠的方案數。
轉移：第 i 顆選已用 j 種中的一種（j 種選擇），或選新第 j 種（K-j+1 種選擇）。

dp[i][j] = j * dp[i-1][j] + (K-j+1) * dp[i-1][j-1]

初始 dp[1][1] = K。答案 Σ_{i=1..N} dp[i][K]。

矩陣快速冪優化

N 太大，需將 i 視為階段，構造轉移矩陣。引入前綴和 g_i = Σ_{t=1..i} dp[t][K] 作為額外狀態。
狀態向量 [g, dp[1], dp[2], ..., dp[K]]^T，維度 K+1。
轉移矩陣 M：

| 1  0  0 ... 0  1 |   // g' = g + dp[K]
| 0  1  0 ... 0  0 |   // dp[1]' = 1*dp[1] + K*dp[0]? 實際見代碼
| 0 K-1 2 ... 0  0 |
| ...            |
| 0  0  0 ... 1  K |

完整代碼結構

const int MOD = 1234567891;
struct Mat { int n; ll v[31][31]; ... };
Mat operator*(Mat a, Mat b) { ... } // 模矩陣乘法
Mat operator^(Mat a, ll k) { ... }  // 快速冪

void init() {
    scanf("%d%d", &n, &k);
    M.n = V.n = k+1;
    M.eye(); V.eye();
    M.v[0][0] = M.v[0][k] = 1;
    for (int i=1; i<=k; i++) {
        if (i>1) M.v[i][i-1] = k-i+1;
        M.v[i][i] = i;
    }
    V.v[1][0] = k; // dp[1][1] = K
}

void solve() {
    Mat R = (M ^ n) * V;
    printf("%lld\n", R.v[0][0]); // g_n
}

關鍵洞察

1. 降維：原 DP 二維 (i,j)，將 i 作為階段，j 作為狀態分量，構造 (K+1) 階矩陣。
2. 前綴和入狀態：答案是求和，引入 g 使矩陣冪直接給出最終答案。
3. 初始向量：對應 i=1 時的狀態 [0, K, 0, ..., 0]^T。

此題是「DP 狀態壓縮 + 矩陣快速冪 + 前綴和技巧」的綜合範例，K ≤ 30 使矩陣維度可控（31^3 log N 极快）。