Codeforces 464C Substitutes in Number：反向 DP 路徑壓縮

Codeforces 464C - 數字替換查詢：反向 DP 路徑壓縮

初始字符串 s，q 個查詢 d→t（將所有數字 d 替換為字符串 t）。最終求結果數字模 1e9+7。|s|, Σ|t| ≤ 1e5。

正向模擬不可行

直接替換會導致字符串指數級增長，且插入刪除操作昂貴。

反向 DP 核心思想

從最後一個查詢倒推到第一個。維護兩個數組：

• val[d]：數字 d 經過當前已處理的查詢後，最終展開的數值（模 MOD）
• len[d]：該展開字符串的長度（對應 10 的冂次，模 MOD）

初始：val[d]=d, len[d]=10。
處理查詢 d→t（反向）：

ll new_val = 0, new_len = 1;
for (char ch : t) {
    int c = ch - '0';
    new_val = (new_val * len[c] + val[c]) % MOD;
    new_len = (new_len * len[c]) % MOD;
}
val[d] = new_val; len[d] = new_len;

最終計算

遍歷原始字符串 s：
ans = (ans * len[c] + val[c]) % MOD

完整代碼

const int MOD = 1e9+7;
char s[100005], qry[100005];
int qid[100005]; string qstr[100005];
int val[10], len[10];
int main() {
    gets(s); int q; scanf("%d\n", &q);
    for (int i=0; i=0; --i) {
        ll nv=0, nl=1;
        for (char ch : qstr[i]) {
            int c = ch-'0';
            nv = (nv * len[c] + val[c]) % MOD;
            nl = (nl * len[c]) % MOD;
        }
        val[qid[i]] = nv; len[qid[i]] = nl;
    }
    ll ans = 0;
    for (char *p=s; *p; ++p)
        ans = (ans * len[*p-'0'] + val[*p-'0']) % MOD;
    printf("%lld\n", ans);
}

關鍵點

• 反向處理 = 路徑壓縮，將多步替換合併為單步
• len[d] 存 10^{展開長度} mod MOD，用於高位拼接
• 時間 O(|s| + Σ|t|)，空間 O(1)（常數 10）
• 注意輸入讀取：gets/scanf 混用需處理換行符