自动搬运

查看原文

来自洛谷，原作者为

	George1123 **

搬运于2025-08-24 21:47:36，当前版本为作者最后更新于2020-02-11 21:21:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

博客中看：题解-[SDOI2014]数数

[SDOI2014]数数

这题的前置知识是AC自动机和dp，前置题目是 [JSOI2007]文本生成器，前置题目我写的题解 题解-[JSOI2007]文本生成器。我的讲解假设你做过上面那道题。

这题比上面那题多个条件，我因此多调了 $3$ 个小时。多的条件：答案要不大于整数 $n$。所以AC自动机部分同上，改变dp部分。

解：$dp[i][j][k]$ 表示文本串（幸运数）长度为 $i$，结尾是AC自动机上的节点 $j$，$k$ 表示这个文本串下一个字符是否受 $n$ 某个数位大小的限制（如果受限制，$k=1$；否则，$k=0$）。$mk[i]$ 表示 $i$ 这个AC自动机上节点是否为某个不幸运的数结尾。

仔细读题会发现：模式串中含有 $0$ 前置，而文本串不能以 $0$ 开头。所以有（所有数组下标从 $1$ 开始，$1\le n[1]\le 9$，因为 $ch[1][i]$ 会有重复所以用 $++$ 而非 $=1$）：

$$dp[1][ch[1][i]][0]++(1\le i<n[1],mk[ch[1][i]]!=1)$$

然后如果上式 $i$ 取 $n[1]$，那么这个字符串的下一位就会受到 $n[2]$ 大小的限制，所以有：

$$dp[1][ch[1][n[1]]][1]++(mk[ch[1][n[1]]]!=1)$$

综上，有代码：

for(int i=1;i<=w[1]-'0';i++)
	if(!mk[ch[1][i]])//不能选到不幸运的子串
		(f[1][ch[1][i]][i==w[1]-'0']+=1)%=mod; //Orz

为了避免算上首位为 $0$ 的文本串，上面的代码没有 $dp[1][ch[1][0]][0]++$。为了计算那些位数小于 $n$ 的文本串，则有：

$$dp[i][ch[1][j]][0]++(2\le i\le \texttt{length of }n,1\le j\le 9,mk[ch[1][j]]!=1) $$

为了防止 $\color{#333399}\texttt{MLE}$，dp用滚动数组，所以有代码：

for(int i=2;i<=m;i++){
	memset(f[i&1],0,sizeof f[i&1]);//滚动数组必须清空
	for(int j=1;j<=9;j++)
		if(!mk[ch[1][j]])
			(f[i&1][ch[1][j]][0]+=1)%=mod;//Orz

初始化完了，重点就来了——递推公式。如果某个文本串合法，那么在它后面加一个字符，如果这个文本串还是 $\le n$ ，并且不包含不幸运的子串，那么它就是合法的。

转化为dp递推式（$cnt$ 表示AC自动机节点个数）：

$$dp[i][ch[j][k]][0]+=dp[i-1][j][0]$$ $$(1\le i\le\texttt{length of }n,1\le j\le cnt,mk[ch[j][k]]!=1,\color{red}0\color{black}\le k\le 9) $$

这里是递推，所以这就相当于在求一个数中间的一个数位，所以可以取 $0$

$$dp[i][ch[j][k]][0]+=dp[i-1][j][1]$$ $$(1\le i\le\texttt{length of }n,1\le j\le cnt,mk[ch[j][k]]!=1,\color{red}0\le k<n[i]\color{black}) $$

除非取的文本串对 $n$ 位位紧逼，要不然下一位就不受 $n$ 数位大小的限制。

$$dp[i][ch[j][n[i]]][1]+=dp[i-1][j][1]$$ $$(1\le i\le\texttt{length of }n,1\le j\le cnt,mk[ch[j][n[i]]]!=1) $$

取的文本串对 $n$ 位位紧逼。

代码：

for(int j=1;j<=cnt;j++){
	if(mk[j]) continue;
	if(f[(i-1)&1][j][0])
		for(int c=0;c<=9;c++)
			if(!mk[ch[j][c]])
				(f[i&1][ch[j][c]][0]+=f[(i-1)&1][j][0])%=mod;
	if(f[(i-1)&1][j][1])
		for(int c=0;c<=w[i]-'0';c++)
			if(!mk[ch[j][c]])
				(f[i&1][ch[j][c]][c==w[i]-'0']+=f[(i-1)&1][j][1])%=mod;
}

最后答案为 $ans$，就有：

$$ans=\sum\limits ^{cnt}_{i=1}dp[\texttt{length of }n][i][0]+dp[\texttt{length of }n][i][1] $$

如果你懂了，蒟蒻就放dp代码了：

void dp(){
	for(int i=1;i<=w[1]-'0';i++)
		if(!mk[ch[1][i]])
			(f[1][ch[1][i]][i==w[1]-'0']+=1)%=mod; //Orz
	for(int i=2;i<=m;i++){
		memset(f[i&1],0,sizeof f[i&1]);
		for(int j=1;j<=9;j++)
			if(!mk[ch[1][j]])
				(f[i&1][ch[1][j]][0]+=1)%=mod;//Orz
		for(int j=1;j<=cnt;j++){
			if(mk[j]) continue;
			if(f[(i-1)&1][j][0])
				for(int c=0;c<=9;c++)
					if(!mk[ch[j][c]])
						(f[i&1][ch[j][c]][0]+=f[(i-1)&1][j][0])%=mod;
			if(f[(i-1)&1][j][1])
				for(int c=0;c<=w[i]-'0';c++)
					if(!mk[ch[j][c]])
						(f[i&1][ch[j][c]][c==w[i]-'0']+=f[(i-1)&1][j][1])%=mod;
		}
	}
	for(int i=1;i<=cnt;i++)
		if(!mk[i]) (((ans+=f[m&1][i][0])%=mod)+=f[m&1][i][1])%=mod;
}

整体代码（dp+AC自动机）：

#include <bits/stdc++.h>
using namespace std;
const int M=1210;
const int L=1510;
const int mod=1e9+7;
class Trie{
public:
	int ch[L][10],cnt;
	bool mk[L];
	Trie(){cnt=1;}
	void insert(char*s){
		int n_junior=strlen(s+1),p=1;
		for(int i=1;i<=n_junior;i++){
			int c=s[i]-'0';
			if(!ch[p][c]) ch[p][c]=++cnt;
			p=ch[p][c];
		}
		mk[p]=1;
	}
};
int n,m,f[2][L][2],ans;
char w[M],s[L];
class Acam:public Trie{
public:
	int fa[L];
	void build(){
		for(int i=0;i<=9;i++) ch[0][i]=1;
		queue<int> q;
		while(q.size()) q.pop(); //我因为没清零WA了5次
		q.push(1);
		while(q.size()){
			int x=q.front();q.pop();
			mk[x]|=mk[fa[x]];
			for(int c=0;c<=9;c++)
				if(ch[x][c]){
					fa[ch[x][c]]=ch[fa[x]][c];
					q.push(ch[x][c]);
				} else ch[x][c]=ch[fa[x]][c];
		}
	}
	void dp(){
		for(int i=1;i<=w[1]-'0';i++)
			if(!mk[ch[1][i]])
				(f[1][ch[1][i]][i==w[1]-'0']+=1)%=mod;
		for(int i=2;i<=m;i++){
			memset(f[i&1],0,sizeof f[i&1]);
			for(int j=1;j<=9;j++)
				if(!mk[ch[1][j]])
					(f[i&1][ch[1][j]][0]+=1)%=mod;
			for(int j=1;j<=cnt;j++){
				if(mk[j]) continue;
				if(f[(i-1)&1][j][0])
					for(int c=0;c<=9;c++)
						if(!mk[ch[j][c]])
							(f[i&1][ch[j][c]][0]+=f[(i-1)&1][j][0])%=mod;
				if(f[(i-1)&1][j][1])
					for(int c=0;c<=w[i]-'0';c++)
						if(!mk[ch[j][c]])
							(f[i&1][ch[j][c]][c==w[i]-'0']+=f[(i-1)&1][j][1])%=mod;
			}
		}
		for(int i=1;i<=cnt;i++)
			if(!mk[i]) (((ans+=f[m&1][i][0])%=mod)+=f[m&1][i][1])%=mod;
	}
}t;
int main(){
	scanf("%s\n%d",w+1,&n),m=strlen(w+1);
	for(int i=1;i<=n;i++)
		scanf("%s",s+1),t.insert(s);
	t.build(); t.dp();
	printf("%d\n",ans);
	return 0;
}

祝大家学习愉快！