LGP3311题解

为什么我和同学对比了一下，发现我和他的做法差别很大啊

对于这种问题，我们把整个字符串分为两个部分：前缀顶着最高位和后缀没有顶着最高位。

我们枚举这个前缀，然后后缀通过 DP 来搞定。

不包含任何一个子串，似乎最有力的处理工具就是 ACAM。

于是我们可以确定这个 DP 的状态：\(dp[k][u]\) 表示从自动机的节点 \(u\) 上走 \(k\) 条边都遇不上被标记点的方案数。

转移：\(dp[k][u]\) 从 \(dp[k-1][trans[u][c]]\) 转移过来就好了。

但是这样会有一个问题：枚举出来的正整数含有前导 \(0\)。

考虑加上被判断成不合法的方案。我们枚举前导 \(0\) 的数量，然后将正整数分为四类：

//加前导0合法 / 不加前导0合法     - a

//加前导0合法 / 不加前导0不合法   - b=0

//加前导0不合法 / 不加前导0合法   - c

//加前导0不合法 / 不加前导0不合法 - d

可以发现我们原本计算的是 \(a+b\)，但是我们需要计算 \(a+c\)。

枚举了前导 \(0\) 后，直接减去 \(a+b\) 然后加上 \(a+c\) 就可以了（

具体的话维护一个节点，每次都往 \(0\) 方向走就行了。

#include<cstring>

#include<cstdio>

#include<cctype>

typedef unsigned ui;

const ui M=1505,mod=1e9+7;

ui n,m,tot(1),dp[M][M],fail[M],trans[M][10];bool vis[M];char s[M],S[M];

inline void Insert(char*s){

	ui u(1);

	while(isdigit(*s)){

		const ui&c=*s-48;*s++=0;

		if(!trans[u][c])trans[u][c]=++tot;

		u=trans[u][c];

	}

	vis[u]=true;

}

inline void Build(){

	static ui L,R,q[M];L=1;

	for(ui c=0;c<10;++c){

		if(trans[1][c])q[++R]=trans[1][c],fail[trans[1][c]]=1;

		else trans[1][c]=1;

	}

	while(L<=R){

		const ui&u=q[L++];

		for(ui c=0;c<10;++c){

			if(trans[u][c])q[++R]=trans[u][c],fail[trans[u][c]]=trans[fail[u]][c];

			else trans[u][c]=trans[fail[u]][c];

		}

	}

	for(ui i=1;i<=R;++i)vis[q[i]]|=vis[fail[q[i]]];

}

signed main(){

	ui ans(0);

	scanf("%s%u",s+1,&n);m=strlen(s+1);

	for(ui i=1;i<=n;++i){

		scanf("%s",S);Insert(S);

	}

	Build();

	for(ui u=1;u<=tot;++u)if(!vis[u])dp[0][u]=1;

	for(ui i=1;i<=m;++i){

		for(ui u=1;u<=tot;++u)if(!vis[u]){

			for(ui c=0;c<10;++c)dp[i][u]=(dp[i][u]+dp[i-1][trans[u][c]])%mod;

		}

	}

	ui u(1),now(1);

	for(ui i=1;i<=m;++i){

		if(vis[u])break;now=trans[now][0];

		for(ui c=0;c<s[i]-48;++c)if(!vis[trans[u][c]])ans=(ans+dp[m-i][trans[u][c]])%mod;

		if(i!=m)for(ui c=1;c<10;++c)ans=(ans+mod+dp[m-i-1][trans[1][c]]-dp[m-i-1][trans[now][c]])%mod;

		u=trans[u][s[i]-48];

	}

	if(!vis[u])++ans,ans==mod&&(ans=0);

	printf("%u",(ans+mod-1)%mod);

}

巴特西

LGP3311题解

最新文章

热门文章