CF585F Digits of Number Pi 题解

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;
}