數位 DP 經典：hihoCoder 1033 交錯和

問題描述

給定區間 [L, R]，求其中所有數字的「交錯和」等於 k 的數的總和。交錯和定義：從最低位開始，交替加減（個位加、十位減、百位加...）。結果模 1e9+7。

數位 DP 狀態設計

dfs(pos, sum, parity, tight, zero)：

• pos：當前處理位（從高位到低位，或反）。
• sum：已處理位的交錯和（偏移 +200 避免負數）。
• parity：當前位是加（0）還是減（1）。
• tight：是否受上界限制。
• zero：是否仍處於前導零階段。

返回結構體 {cnt, sum}：符合條件的數字個數、這些數字的總和（模 MOD）。

轉移與合併

for (int d = 0; d <= up; d++) {
    if (zero && d==0) cur = dfs(pos-1, sum, parity, tight&&d==up, 1);
    else {
        int ns = parity==0 ? sum+d : sum-d;
        cur = dfs(pos-1, ns, parity^1, tight&&d==up, 0);
    }
    ll ways = cur.cnt;
    ll val = (cur.sum + ways * (d * pow10[pos] % MOD)) % MOD;
    ans.cnt = (ans.cnt + ways) % MOD;
    ans.sum = (ans.sum + val) % MOD;
}

關鍵細節

• 前導零不計入交錯和，zero 狀態保持 parity 不變。
• 最終判斷：pos==0 時，若 zero 或 sum != k+200 則 cnt=0，否則 cnt=1, sum=0（單個數值在上層累加）。
• 預計算 pow10[i] = 10^i % MOD。
• 記憶化：!tight && !zero 時用 dp[pos][sum][parity][k]。

複雜度

位數 ≤ 19，和範圍 ±200（401），parity 2，k 固定。狀態數 19*401*2 ≈ 1.5e4，極快。