洛谷 P10167 [DTCPC 2024] 小方学乘法 题解

想法比较直接的优化 dp + 插值。

首先由于 $x$ 的插入会导致原来的数的错位，因此一个显然的想法是对于位数不同的 $x$ 分别处理。

然后注意到当 $x$ 的位数固定时，对于任意一种 $x$ 和乘号的填法，得到的乘法算式中的每一个数的值都是一个常数或者关于 $x$ 的一次函数。于是将它们乘起来就会得到一个 $x$ 的 $O(n)$ 次多项式。对所有填入乘号和 $x$ 的方法求和并不改变多项式的次数。至此我们可以考虑对若干个 $x$ 单独求值并通过多项式插值快速求和。

我们需要对一个固定的 $x$（记这个 $x$ 的位数为 $l$）在 $O(n)$ 时间内计算答案。考虑一个 dp，设 $f_i$ 为考虑到第 $i$ 个问号之前的部分，所有填法的计算结果的和。暴力的转移是枚举最后一个乘号的位置（设为 $j$），并将 $f_j$ 乘上后面所有位置填 $x$ 构成的数转移到 $f_i$。这样是 $O(n^2)$ 的，考虑优化。

注意到 $j$ 转移到的位置从 $i$ 变为 $i+1$ 时，$f_j$ 乘上的值的变化一定是先乘上「$x$ 的位数」个 $10$，加上 $x$，再乘上「第 $i$ 个问号和第 $i+1$ 个问号之间的数字串长度」个 $10$，再加上这串数字构成的值。所以我们在转移过程中维护 $f_j$ 的和以及 $f_j$ 乘上后面的值的和两个值，就可以 $O(n)$ 完成上述 dp 了。具体可以看代码。

对每一个位数取出 $O(n)$ 个点值，求前缀和之后插值即可。暴力插值或线性插值均可。复杂度 $O(n^2\log R)$。

#include <bits/stdc++.h>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
    char c = getchar();
    int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

const long long mod = 1000000007;
const int N = 2005, L = 18;

int n;
char str[N];
vector <pair <long long, int> > val;
long long f[N], pw10[N], p10r[N], sl, sr, x[N], y[N], inv[N];

inline void Prefix() {
    long long cur = 0, len = 0;
    for (int i = 1;i <= n;i++) {
        if (str[i] == '?') {
            val.push_back(make_pair(cur, len));
            cur = 0; len = 0;
        } else {
            cur = (cur * 10 + str[i] - '0') % mod;
            len++;
        }
    }
    val.push_back(make_pair(cur, len));
    pw10[0] = 1;
    for (int i = 1;i <= n;i++) pw10[i] = pw10[i - 1] * 10 % mod;
    p10r[0] = 1;
    for (int i = 1;i <= L;i++) p10r[i] = p10r[i - 1] * 10;
    inv[1] = 1;
    for (int i = 2;i <= n;i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}

inline long long getAns(long long x, long long xln) {
    x %= mod;
    long long fsm = 0, fpsm = 0;
    f[0] = val[0].first;
    fsm = 1;
    fpsm = val[0].first;
    for (int i = 1;i < val.size();i++) {
        fpsm = fpsm * pw10[xln] % mod;
        fpsm = (fpsm + x * fsm) % mod;
        fpsm = fpsm * pw10[val[i].second] % mod;
        fpsm = (fpsm + val[i].first * fsm) % mod;
        f[i] = (fpsm + f[i - 1] * val[i].first) % mod;
        fsm = (fsm + f[i - 1]) % mod;
        fpsm = (fpsm + f[i - 1] * val[i].first) % mod;
    }
    return f[val.size() - 1];
}

inline long long Inv(long long x) {
    if (x < 0) return mod - inv[-x];
    else return inv[x];
}

inline void Solve() {
    long long ans = 0;
    for (int i = 1;i <= L;i++) {
        long long vl = p10r[i - 1], vr = p10r[i] - 1;
        vl = max(vl, sl); vr = min(vr, sr);
        if (vl > vr) continue;
        long long cnt = val.size() + 5;
        if (vr - vl + 1 <= cnt) {
            for (long long j = vl;j <= vr;j++) ans = (ans + getAns(j % mod, i)) % mod;
        } else {
            y[0] = 0;
            for (long long j = vl;j <= vl + cnt - 1;j++) {
                x[j - vl + 1] = j;
                y[j - vl + 1] = getAns(j % mod, i);
            }
            for (int j = 1;j <= cnt;j++) y[j] = (y[j] + y[j - 1]) % mod;
            for (int j = 1;j <= cnt;j++) {
                long long cur = y[j];
                for (int k = 1;k <= cnt;k++) {
                    if (k == j) continue;
                    cur = cur * (vr % mod - x[k] % mod) % mod * Inv(x[j] - x[k]) % mod;
                }
                ans = (ans + cur) % mod;
            }
        }
    }
    cout << (ans % mod + mod) % mod << endl;
}

int main() {
    cin >> str + 1; n = strlen(str + 1);
    cin >> sl >> sr;
    Prefix();
    Solve();
    return 0;
}