[BZOJ3530/Luogu3311][SDOI2014]数数(AC自动机,数位动态规划)

发布于 2018-03-24  58 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3530/Luogu3311][SDOI2014]数数(AC自动机,数位动态规划)

Description

我们称一个正整数N是幸运数,当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22,333,0233)时,233是幸运数,2333、20233、3223不是幸运数。
给定N和S,计算不大于N的幸运数个数

Tag

AC自动机,数位动态规划

解决思路

把数字串插入到AC自动机中,那么首先我们知道,在匹配构造的时候,是不能走到单词结尾的地方的。
然后我们先算位数小于 N 的位数的方案数。设 F[i][j] 表示构造到第 i 位当前在 AC 自动机的第 j 号点的方案数,那么向它的所有不是数字串结尾的儿子转移即可。
再考虑位数严格等于 N 的方案数,那么类似数位 DP 里的做法,设F[i][j][0/1] 其中 [0] 表示严格小于,[1] 表示严格等于的方案数。那么转移的时候严格等于的就只枚举到对应的 N 中的那一位转移,而小于的则可以在整个字符集中转移,分别讨论一下。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=101;
const int maxTrie=1700;
const int maxAlpha=10;
const int Mod=1e9+7;
const int inf=2147483647;

class TrieData
{
public:
    int fail,end;
    int son[maxAlpha];
};

int nodecnt=0,Queue[maxTrie];
char N[maxTrie],str[maxTrie];
TrieData T[maxTrie];
ll F[maxTrie][maxTrie][2];

void Insert(char *s);
void GetFail();

int main()
{
    scanf("%s",N+1);
    int n;scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",str+1);
        Insert(str);
    }
    GetFail();//构建AC自动机
    int L=strlen(N+1);
    //先计算长度小于N的长度的方案,这时不需要考虑小于N的限制,因为一定小于
    F[0][0][0]=1;
    for (int i=0;i<L;i++)
        for (int j=0;j<=nodecnt;j++)
        {
            if (T[j].end!=0) continue;//单词结尾无转移
            if (F[i][j][0])
            {
                for (int c=(i==0)?(1):(0);c<maxAlpha;c++)
                    if (T[T[j].son[c]].end==0)//向所有非单词结尾的儿子转移
                        F[i+1][T[j].son[c]][0]+=F[i][j][0],F[i+1][T[j].son[c]][0]%=Mod;
            }
        }
    ll Ans=0;//累加到答案中
    for (int i=1;i<L;i++) for (int j=0;j<=nodecnt;j++) if (T[j].end==0) Ans=(Ans+F[i][j][0])%Mod;
    mem(F,0);//然后开始计算长度等于N的长度的方案
    F[0][0][0]=1;//[0]危险态,[1]安全态
    for (int i=0;i<L;i++)
    {
        for (int j=0;j<=nodecnt;j++)
        {
            if (T[j].end!=0) continue;
            if (F[i][j][0])//危险态转移
            {
                for (int c=(i==0)?(1):(0);c<N[i+1]-'0';c++)
                    if (T[T[j].son[c]].end==0) F[i+1][T[j].son[c]][1]+=F[i][j][0],F[i+1][T[j].son[c]][1]%=Mod;//危险态->安全态转移
                if (T[T[j].son[N[i+1]-'0']].end==0) F[i+1][T[j].son[N[i+1]-'0']][0]+=F[i][j][0],
                                                        F[i+1][T[j].son[N[i+1]-'0']][0]%=Mod;//危险态->危险态转移
            }
            if (F[i][j][1])
                for (int c=(i==0)?(1):(0);c<maxAlpha;c++)
                    if (T[T[j].son[c]].end==0) F[i+1][T[j].son[c]][1]+=F[i][j][1],
                                                   F[i+1][T[j].son[c]][1]%=Mod;//安全态->安全态转移

        }
    //累加答案
    for (int i=0;i<=nodecnt;i++) if (T[i].end==0) Ans+=F[L][i][0]+F[L][i][1],Ans%=Mod;
    printf("%lld\n",Ans);
    return 0;
}

void Insert(char *s)
{
    int len=strlen(s+1);
    int now=0;
    for (int i=1;i<=len;i++)
    {
        if (T[now].son[s[i]-'0']==0) T[now].son[s[i]-'0']=++nodecnt;
        now=T[now].son[s[i]-'0'];
    }
    T[now].end=1;
    return;
}

void GetFail()
{
    int h=0,t=0;
    for (int i=0;i<maxAlpha;i++) if (T[0].son[i]) Queue[++h]=T[0].son[i];
    while (t!=h)
    {
        int u=Queue[++t];
        for (int i=0;i<maxAlpha;i++)
            if (T[u].son[i])
            {
                T[T[u].son[i]].fail=T[T[u].fail].son[i];
                T[T[u].son[i]].end|=T[T[T[u].fail].son[i]].end;
                Queue[++h]=T[u].son[i];
            }
            else T[u].son[i]=T[T[u].fail].son[i];
    }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3530/Luogu3311][SDOI2014]数数(AC自动机,数位动态规划)


HNCJ OIer