(IOICamp) 86. 秘密讀書會 [AC自動機的DP]

https://judge.ioicamp.org/problems/86

AC自動機的DP。

把AC自動機上面的點當作狀態去DP，隨時統計到達當前狀態的方法數。

注意到達 Si 的時候，要把dp設為0，因為不能到達。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL,LL>  pii;
typedef pair<pii,LL> piii;
#define F first
#define S second
const LL mod = 1e9 + 7;
const int N = 106;

struct AC_Automata {
    static const int N = 2e4 + 6;
    static const int M = 106;
    static const int SIGMA = 26;
    LL dp[M][N];
    int ch[N][SIGMA];
    int val[N];
    int sz;
    int last[N],fail[N];
    int que[N],qs,qe;
    void init()
    {
        sz = 1;
        memset(ch[0],0,sizeof(ch[0]));
        qs = qe  = 0;
        memset(val,0,sizeof(val));
        memset(last,0,sizeof(last));
    }
    int idx(char c)
    {
        return c-'a';
    }
    int insert(string s,int v)
    {
        int now=0;
        int n=s.size();
        for (int i=0;n>i;i++)
        {
            int c=idx(s[i]);
            if (!ch[now][c])
            {
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz] = 0;
                ch[now][c] = sz++;
            }
            now = ch[now][c];
        }
        val[now] = v;
        return now;
    }
    void print(int j)
    {
        if (j)
        {
            //now we match string v[j]
            print(last[j]);  //may match multiple strings
        }
    }
    void getFail()
    {
        qs=0,qe=0;
        fail[0]=0;
        for (int c=0;SIGMA >c;c++)
        {
            int now=ch[0][c];
            if (now)
            {
                fail[now] = 0;
                que[qe++] = now;
                last[now] = 0;
            }
        }
        while (qs != qe)
        {
            int t=que[qs++];
            for (int c=0;SIGMA > c;c++)
            {
                int now=ch[t][c];
                if (!now) continue;
                que[qe++] = now;
                int v=fail[t];
                while (v && !ch[v][c]) v=fail[v];
                fail[now] = ch[v][c];
                last[now] = val[ fail[now] ]? fail[now]:last[ fail[now] ];
            }
        }
    }
    void Find(string s)
    {
        getFail();
        //cout<<"qe = "<<qe<<endl;
        int n=s.size();
        int now=0;
        for (int i=0;n>i;i++)
        {
            int c=idx(s[i]);
            while (now && !ch[now][c]) now = fail[now];
            now = ch[now][c];
        }
    }
    void AC_evolution()
    {
        for (qs=0;qs!=qe;)
        {
            int now=que[qs++];
            for (int i=0;SIGMA>i;i++)
            {
                if (ch[now][i] == 0) ch[now][i] = ch[fail[now]][i];
            }
        }
    }
    LL get_answer(int n)
    {
        memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        for (int i=0;n-1>=i;i++)
        {
            for (int j=0;sz>j;j++)
            {
                for (int c=0;SIGMA>c;c++)
                {
                    int nxt = ch[j][c];
                    if (!val[nxt] && !last[nxt])
                    {
                        dp[i+1][nxt] += dp[i][j];
                        dp[i+1][nxt] %= mod;
                    }
                }
            }
        }
        LL ret =0 ;
        for (int j=0;sz>j;j++)
        {
            ret += dp[n][j];
            ret %= mod;
        }
        return ret%mod;
    }
} ac;

string s[N];
int ed[N];

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int n,m;
        cin >> n >> m;
        ac.init();
        for (int i=1;m>=i;i++)
        {
            cin >> s[i];
            ed[i] = ac.insert(s[i],i);
        }
        ac.getFail();
        ac.AC_evolution();
        cout<<ac.get_answer(n)<<endl;
    }
}