bzoj1030: [JSOI2007]文本生成器（AC自动机+DP）

时间：2022-11-14 04:43:58

　　第一次写这类题...懵

　　直接计算答案不好计算，所以补集转化求不合法的方案。

　　首先考虑朴素的DP，设$f(i, s)$表示前$i$个字符，字符串为$s$的方案数，且任意一个给定串都不存在$s$中。

　　我们知道在一个字符串里找其他的字符串是AC自动机的强项，那么我们就可以考虑在AC自动机上跑DP，每次$+j$都在AC自动机上匹配，如果匹配到单词结尾的话就不能转移，否则就是可以转移的。

　　所以设$f(i, j)$为前$i$个字符，当前匹配到AC自动机上第$j$个节点的方案数，如果沿着fail一直往上的所有节点都不是单词结尾就可以转移了。

　　注意是大写字母T_T

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#define MOD(x) ((x)>=mod?(x)-mod:(x))

#define ll long long

using namespace std;

const int maxn=, maxm=, mod=;

struct poi{int nxt[], fail;}tree[maxn*maxm];

int n, m, ans, tott;

int f[maxm][maxn], h[maxn];

bool cnt[maxn];

char s[maxm];

inline void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-'&&(f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', c=getchar();

    k*=f;

}

inline void insert()

{

    int len=strlen(s+), now=;

    for(int i=, ch;i<=len;i++)

    {

        if(!tree[now].nxt[ch=s[i]-'A'])

        tree[now].nxt[ch]=++tott;

        now=tree[now].nxt[ch];

    }

    cnt[now]=;

}

inline void getfail()

{

    int front=, rear=; tree[].fail=-;

    for(int i=, too;i<;i++)

    if((too=tree[].nxt[i])) h[++rear]=too;

    while(front<=rear)

    {

        int now=h[front++];

        for(int i=, too;i<;i++)

        if((too=tree[now].nxt[i]))

        tree[too].fail=tree[tree[now].fail].nxt[i], h[++rear]=too;

        else tree[now].nxt[i]=tree[tree[now].fail].nxt[i];

        cnt[now]|=cnt[tree[now].fail];

    }

}

int main()

{

    read(n); read(m);

    for(int i=;i<=n;i++) scanf("%s", s+), insert();

    getfail(); f[][]=;

    for(int i=;i<=m;i++)

    for(int j=;j<=tott;j++)

    if(!cnt[j]) for(int k=;k<;k++)

    f[i][tree[j].nxt[k]]=MOD(f[i][tree[j].nxt[k]]+f[i-][j]);

    for(int i=;i<=tott;i++) if(!cnt[i]) ans=MOD(ans+f[m][i]);

    int tot=; for(int i=;i<=m;i++) tot=1ll*tot*%mod;

    printf("%d\n", MOD(tot-ans+mod));

}

相关文章