[SDOI2014][JZOJ3624]數數

題目大意

求不大于 N 的正整數中，看作字元串（不包含字首0）後，沒有子串屬于給定字元串集 S 的數的個數。

1≤N<101200,|S|≤100,∑s∈S|s|≤1500

題目分析

不大于某個數，然後對于數字的某些位有特殊要求，這是經典的數位dp模型。

那如何解決子串的限制條件呢？可以發現限制條件相當于多串比對。那我們考慮就 S 集合建立AC自動機，然後通過确定目前狀态在自動機内的指針，來确定狀态是否合法。

在建立自動機，處理 fail 數組時，我們同時處理布爾數組 markx ，表示節點 x 及其fail指針指向節點（可以指多次）中是否有标記為單詞的。

我們從高位往低位（字元串前往後）枚舉，設 fi,j,0..1 表示枚舉到第 i 位，目前狀态在自動機内的j節點，目前組成的數小于（等于） N 的方案數。

我們枚舉i的合法狀态向 i+1 轉移，狀态合法當且僅當 markj 為 false 。 fi,j,0 可以轉移到 fi+1,nextj,k,0(k∈[0,9]) ， fi,j,1 可以轉移到 fi+1,nextj,Ni+1,1 和 fi+1,nextj,k,0(k∈[0,Ni+1)) 。其中 Ni 表示 N 看成字元串後第i位的數值。

注意不能有前導 0 ，但是仍需考慮不足數位的情況。是以我們還可以在每次i轉移到 i+1 時，順便轉移 fi+1,next[root][k],0 ，也就是這一位開始有大于 0 的數。

設N共有 n 位，自動機節點數為tot，最後答案固然為 ∑i<=toti=0fn,i,0+fn,i,1(marki=false) 。

時間複雜度即為 O(n×tot) 。

代碼實作

作者閑得蛋疼，開了滾動數組，空間大跳樓。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int P=;
const int N=;
const int L=;

int f[][L+][];
queue<int> Q;
char n[N+];
int d,ans,m;

const int W=;

char str[L+];

struct AC_automation
{
    int fail[L+],next[L+][W];
    bool mark[L+];
    int tot,root;

    int newnode()
    {
        fail[tot]=-;
        for (int i=;i<W;i++)
            next[tot][i]=-;
        mark[tot]=false;
        return tot++;
    }

    void init()
    {
        tot=;
        root=newnode();
    }

    void insert()
    {
        int l=strlen(str),rt=root;
        for (int i=;i<l;i++)
            if (next[rt][str[i]-'0']!=-)
                rt=next[rt][str[i]-'0'];
            else
            {
                next[rt][str[i]-'0']=newnode();
                rt=next[rt][str[i]-'0'];
            }
        mark[rt]=true;
    }

    void build()
    {
        for (int i=;i<W;i++)
            if (next[root][i]==-)
                next[root][i]=root;
            else
            {
                fail[next[root][i]]=root;
                Q.push(next[root][i]);
            }
        while (!Q.empty())
        {
            int rt=Q.front();
            Q.pop();
            mark[rt]|=mark[fail[rt]];
            for (int i=;i<W;i++)
                if (next[rt][i]==-)
                    next[rt][i]=next[fail[rt]][i];
                else
                {
                    fail[next[rt][i]]=next[fail[rt]][i];
                    Q.push(next[rt][i]);
                }
        }
    }

    void dp()
    {
        int now=,tsf=;
        for (int i=;i<n[]-'0';i++)
            f[tsf][next[root][i]][]++;
        f[tsf][next[root][n[]-'0']][]++;
        for (int i=;i<d-;i++)
        {
            now^=,tsf^=;
            memset(f[tsf],,sizeof f[tsf]);
            for (int j=;j<W;j++)
                f[tsf][next[root][j]][]++;
            for (int j=;j<tot;j++)
                if (!mark[j])
                {
                    (f[tsf][next[j][n[i+]-'0']][]+=f[now][j][])%=P;
                    for (int k=;k<n[i+]-'0';k++)
                        (f[tsf][next[j][k]][]+=f[now][j][])%=P;
                    for (int k=;k<W;k++)
                        (f[tsf][next[j][k]][]+=f[now][j][])%=P;
                }
        }
        ans=;
        for (int i=;i<tot;i++)
            if (!mark[i])
                (((ans+=f[tsf][i][])%=P)+=f[tsf][i][])%=P;
    }
}atm;

int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    scanf("%s",n);
    d=strlen(n);
    atm.init();
    scanf("%d",&m);
    for (int i=;i<=m;i++)
    {
        scanf("%s",str);
        atm.insert();
    }
    atm.build();
    atm.dp();
    printf("%d\n",ans);
    fclose(stdin);
    fclose(stdout);
}