ACAM+DP 数数 P3311题解

· · 题解

为什么没有人用我这种神秘做法（

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

我们枚举这个前缀，然后后缀通过 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);
}