CF585F Digits of Number Pi

题目

把\(s\)串所有长度为\(\lfloor \frac{d}{2}\rfloor\)的子串插入一个ACAM中，之后数位dp就好了，状态是\(dp_{i,j,0/1}\)第\(i\)位，在ACAM上的节点\(j\)，不卡/卡上界；正难则反一下，统计所有不能被表示即没有经过结束标记的路径即可

注意前导0的处理

代码

#include<bits/stdc++.h>

#define re register

#define LL long long

const int mod=1e9+7;

char S[1005],A[55],B[55];int d;

int fa[1005*50],son[1005*50][10],f[1005*50],cnt;

int dp[2][1005*25][2],n,lm[55];

inline int dqm(int x) {return x<0?x+mod:x;}

inline int qm(int x) {return x>=mod?x-mod:x;}

inline void ins(int l,int r) {

	int nw=0;

	for(re int i=l;i<=r;++i) {

		if(!son[nw][S[i]-'0']) son[nw][S[i]-'0']=++cnt;

		nw=son[nw][S[i]-'0'];

	}

	f[nw]=1;

}

inline int solve(char *H) {

	int ans=0;

	for(re int i=1;i<=d;i++) lm[i]=H[d-i+1]-'0';

	for(re int i=d;i;i--) ans=10ll*ans%mod,ans=qm(ans+lm[i]);

	int o=0;memset(dp,0,sizeof(dp));dp[0][0][1]=1;

	for(re int i=d;i;--i,o^=1) {

		memset(dp[o^1],0,sizeof(dp[o^1]));

		for(re int j=0;j<=cnt;++j) {

			if(!dp[o][j][0]) continue;

			for(re int k=0;k<=9;++k) {

				if(f[son[j][k]]) continue;

				dp[o^1][son[j][k]][0]=qm(dp[o^1][son[j][k]][0]+dp[o][j][0]);

			}

		}

		for(re int j=0;j<=cnt;++j) {

			if(!dp[o][j][1]) continue;

			for(re int k=0;k<lm[i];++k) {

				if(f[son[j][k]]) continue;

				dp[o^1][son[j][k]][0]=qm(dp[o^1][son[j][k]][0]+dp[o][j][1]);

			}

			if(!f[son[j][lm[i]]])

				dp[o^1][son[j][lm[i]]][1]=qm(dp[o^1][son[j][lm[i]]][1]+dp[o][j][1]);

		}

		if(i==d&&!f[son[0][0]]) dp[o^1][son[0][0]][0]=dqm(dp[o^1][son[0][0]][0]-1);

		if(i!=d) {

			for(re int j=1;j<=9;j++) {

				if(f[son[0][j]]) continue;

				dp[o^1][son[0][j]][0]=qm(dp[o^1][son[0][j]][0]+1);

			}

		}

	}

	for(re int i=0;i<=cnt;i++) ans=dqm(ans-dp[o][i][0]),ans=dqm(ans-dp[o][i][1]);

	return ans;

}

inline int chk(char *H) {

	int nw=0;

	for(re int i=1;i<=d;i++) {nw=son[nw][H[i]-'0'];if(f[nw]) return 1;}

	return 0;

}

int main() {

	scanf("%s",S+1);n=strlen(S+1);scanf("%s",A+1);scanf("%s",B+1);d=strlen(A+1);

	for(re int i=1;i+(d>>1)-1<=n;i++) ins(i,i+(d>>1)-1);

	std::queue<int> q;

	for(re int i=0;i<=9;i++) if(son[0][i]) q.push(son[0][i]);

	while(!q.empty()) {

		int k=q.front();q.pop();f[k]|=f[fa[k]];

		for(re int i=0;i<=9;i++)

			if(son[k][i])fa[son[k][i]]=son[fa[k]][i],q.push(son[k][i]);else son[k][i]=son[fa[k]][i];

	}

	printf("%d\n",(solve(B)-solve(A)+mod+chk(A))%mod);

 	return 0;

}

巴特西

CF585F Digits of Number Pi

最新文章

热门文章