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