Codeforces 464C Substitutes in Number：逆向構造 + 快速冪

題目大意

初始字符串 s（長 ≤ 1e5）。n 次操作，每次將數字 x (0-9) 替換為字符串 t。求最終字符串對 1e9+7 取模的數值。直接模擬長度指數增長不可行。

核心思想：逆向處理 + 數值/長度雙維护

定義 f[i][d] = 執行第 i..n 操作後，數字 d 變成的數值模 MOD與長度模 (MOD-1)（費馬小定理，冪次模 MOD-1）。

• 初始：f[n+1][d] = (d, 1)。
• 逆序 i = n..1：
  若 op[i].x != d：f[i][d] = f[i+1][d]。
  否則：將替換串 t 中每字符 c 映射為 f[i+1][c]，合併：
  val = Σ val_c * 10^{len_suffix}，
  len = Σ len_c。

合併公式

pair<int,int> calc(string t, pair<int,int> nxt[10]) {
    long long val = 0, len = 0;
    for (int i = t.size()-1; i >= 0; --i) {
        int d = t[i]-'0';
        val = (val + nxt[d].first * powmod(10, len)) % MOD;
        len = (len + nxt[d].second) % (MOD-1);
    }
    return {val, len};
}

完整代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7, MAXN = 100100;
using pii = pair;
pii f[MAXN][10];
int op_dig[MAXN];
string op_str[MAXN];

long long qpow(long long a, long long e) {
    long long r = 1;
    while (e) { if (e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; }
    return r;
}
pii combine(const string& s, pii nxt[10]) {
    long long val = 0, len = 0;
    for (int i = (int)s.size()-1; i >= 0; --i) {
        int d = s[i]-'0';
        val = (val + nxt[d].first * qpow(10, len)) % MOD;
        len = (len + nxt[d].second) % (MOD-1);
    }
    return {(int)val, (int)len};
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; cin >> s;
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        string line; cin >> line;
        op_dig[i] = line[0]-'0';
        op_str[i] = line.substr(3);  // 格式 "d->t"
    }
    for (int d = 0; d < 10; ++d) f[n+1][d] = {d, 1};
    for (int i = n; i >= 1; --i) {
        for (int d = 0; d < 10; ++d) {
            if (op_dig[i] != d) f[i][d] = f[i+1][d];
            else f[i][d] = combine(op_str[i], f[i+1]);
        }
    }
    pii ans = combine(s, f[1]);
    cout << ans.first << '\n';
    return 0;
}

複雜度

• 時間：O((|s| + Σ|t|) * log MOD)，log MOD 來自快速冪。
• 空間：O(n * 10) 存儲 DP 表。

關鍵技巧總結

1. 逆向 DP：從最後操作倒推，避免字符串指數增長。
2. 雙維狀態：同時維護數值模 MOD 與長度模 MOD-1（費馬小定理降冪）。
3. 快速冪預計算：10^k mod MOD 可預處理加速。