Visits: 368

CF585F Digits of Number Pi

题意

• 给定长度为 $n$ 的数字串 $s$ 和长度为 $d$ 的不含前导零的数字串 $x,y(x \le y)$。
• 求存在长度至少为 $\left\lfloor\frac{d}{2}\right\rfloor$ 的子串是 $s$ 的子串的数字串 $t \in [x,y]$ 的数量。
• $n \le 10^3$，$d \le 50$，答案对 $10^9+7$ 取模。

题解

把 $s$ 所有长度为 $\left\lfloor\frac{d}{2}\right\rfloor$ 的子串拿出来建 AC 自动机，然后数位 dp 即可。

设 $f[i][j][1/0]$ 表示考虑到第 $i$ 位，在 AC 自动机的 $j$ 节点，是否 $(1/0)$ 有上界限制时的方案数，预处理出 $p[i][1/0]$ 为第 $i \sim d$ 位是否 $(1/0)$ 有上界限制时的方案数。

初始时 $f[0][1][1] = 1$。

枚举下一位的数字 $k$，设 $j\to k$ 为 AC 自动机中 $j$ 节点的第 $k$ 个儿子，设限制数字为 $c$。

• 任意时刻有 $f[i][j][0] \to f[i+1][j\to k][0]$；
• 若 $k < c$，则 $f[i][j][1] \to f[i+1][j\to k][0]$；
• 若 $k=c$，则 $f[i][j][1] \to f[i+1][j\to k][1]$；

最后用乘法原理将每种方案的 $f,p$ 相乘即可，时间复杂度 $\mathcal O(10nd^2)$。

代码

const int N = 1e3 + 7, D = 53, K = 11;
int n, d, trie[N*D][K], ed[N*D], fail[N*D], tot = 1;
char s[N], a[D], b[D];
modint p[N][2], f[D][N*D][2];

inline void build() {
    int m = d / 2;
    for (int i = 1; i + m - 1 <= n; i++) {
        int p = 1;
        for (int j = i, k = 1; k <= m; j++, k++) {
            int c = s[j] - '0';
            if (!trie[p][c]) trie[p][c] = ++tot;
            p = trie[p][c];
        }
        ed[p] = 1;
    }
    queue< int > q;
    for (int i = 0; i < 10; i++)
        if (trie[1][i]) fail[trie[1][i]] = 1, q.push(trie[1][i]);
        else trie[1][i] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < 10; i++)
            if (trie[x][i]) fail[trie[x][i]] = trie[fail[x]][i], q.push(trie[x][i]);
            else trie[x][i] = trie[fail[x]][i];
    }
}

inline modint calc(char *t) {
    p[d+1][0] = p[d+1][1] = 1;
    for (int i = d; i; i--) p[i][0] = p[i+1][0] * 10, p[i][1] = (t[i] - '0') * p[i+1][0] + p[i+1][1];
    modint ans = 0;
    for (int i = 1; i <= d; i++)
        for (int j = 1; j <= tot; j++)
            for (int k = 0; k < 2; k++)
                f[i][j][k] = 0;
    f[0][1][1] = 1;
    for (int i = 0; i < d; i++)
        for (int j = 1; j <= tot; j++)
            if (!ed[j])
                for (int k = 0; k < 10; k++) {
                    int o = trie[j][k];
                    f[i+1][o][0] += f[i][j][0];
                    if (k < t[i+1] - '0') f[i+1][o][0] += f[i][j][1];
                    if (k == t[i+1] - '0') f[i+1][o][1] += f[i][j][1];
                }
    for (int i = 1; i <= d; i++)
        for (int j = 1; j <= tot; j++)
            if (ed[j]) ans += f[i][j][0] * p[i+1][0] + f[i][j][1] * p[i+1][1];
    return ans;
}

int main() {
    rds(s, n), rds(a, d), rds(b, d), build();
    int k = d;
    while (a[k] == '0') a[k--] = '9';
    --a[k];
    print(calc(b) - calc(a));
    return 0;
}