夏晓光(loveJY)的博客

IOI2020集训队作业

其实一开始没把他当做集训队作业去做的,没想到清北的老师是集训队作业推送带师...

封面图的小姐姐为什么有角...

• 给定长度为 $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$ 取模。

首先这个大小在[x,y]之间一定是一个数位DP啊...而且是$O(d)$长度的数位DP

其次我们还要求一定出现在s中?直接DP好像不太行,所以我们考虑转化为是s一个子串

那么我们有一个显然的做法,把s中所有长度在$\left\lfloor\frac{d}{2}\right\rfloor$ 到 $d$的所有串建一个AC自动机,然后要求就是能在自动机上匹配完成的一个串

再仔细想一下我们只需要把长度为$\left\lfloor\frac{d}{2}\right\rfloor$的子串提出来就好,因为如果匹配了的串长度大于$\left\lfloor\frac{d}{2}\right\rfloor$我们一定可以匹配一个$\left\lfloor\frac{d}{2}\right\rfloor$的串啊

嗯...现在我们可以着手设计DP状态了

$f[i][j][0/1]$表示我现在dp到了i这个位置,匹配到了AC自动机上j号节点,有没有卡上上界

转移时标准的枚举下一个字符是啥,设为c

case 1如果j有c这个儿子

那么j->ch[j][c],i到i+1,然后对于0/1这一维,如果之前为1而且c是上界,我们就转移到1,否则转移到0

case 2 如果j没有c这个儿子

这种情况其实比较难算,如果直接从j号点跳fail的话我们还需要知道现在有没有出现一个匹配完成的串,时间复杂度也可能不太对,所以我们考虑把这中情况提出来弄

我们处理出一个叫做p[i][0/1]的数组,表示从长度为1~d-i+1的,有没有卡上上界的随便填的串总方案数

然后你会发现如果AC自动机有个节点是ed的话我们就枚举一个长度然后把$f[i][ed][0]*p[i+1][0]+f[i][ed][1]*p[i+1][1]$计入答案

拆开处理,在变化处统计,这也是对于某一维是0/1的一种很不错的处理方式啊qwq

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 1e9 + 7;
const int MAXN = 1e3 + 7, D = 53, K = 11;
int n, d, trie[MAXN * D][K], ed[MAXN * D], fail[MAXN * D], T = 1;
char s[MAXN], a[D], b[D];
ll p[MAXN][2], f[D][MAXN * 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] = ++T;
			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];
			//AC自动机,广搜实现fail
		}
	}
}

inline ll 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;
		p[i][1] = ((t[i] - '0') * p[i + 1][0] % P + p[i + 1][1]) % P;
        //p数组处理方法,真的是直接填啊qwq
	}
	ll ans = 0;
	for(int i = 1; i <= d; ++i) {
		for(int j = 1; j <= T; ++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 <= T; ++j) {
			if(!ed[j]) {
				for(int k = 0; k < 10; ++k) {
					int o = trie[j][k];
					(f[i + 1][o][0] = (f[i + 1][o][0] + f[i][j][0]) % P);
					if(k < t[i + 1] - '0')(f[i + 1][o][0] = (f[i + 1][o][0] + f[i][j][1]) % P);
					if(k == t[i + 1] - '0')(f[i + 1][o][1] = (f[i + 1][o][1] + f[i][j][1]) % P);
					// assert(f[i + 1][o][0] >= 0);
					// assert(f[i + 1][o][1] >= 0);
//知道为什么asssert了吗?因为最后一步我们+P)%P0pts了/ll
				}
			}
		}
	}
	for(int i = 1; i <= d; ++i) {
		for(int j = 1; j <= T; ++j) {
			if(ed[j]) {
				ans = (ans + (f[i][j][0] * p[i + 1][0] % P + f[i][j][1] * p[i + 1][1] % P) % P) % P;
				// assert(ans >= 0);
			}
		}
	}
	ans %= P;
	return ans;
}


int main() {
	cin >> s + 1;
	cin >> a + 1;
	cin >> b + 1;
	n = strlen(s + 1);
	d = strlen(a + 1);
	build();
	int k = d;
	while(a[k] == '0')a[k--] = '9';
	--a[k];
	printf("%lld\n", ((calc(b) - calc(a)) % P + P) % P );
	return 0;
}

我就是那$1/45$qwq