ABC_419_F - All Included
空降
一道AC自动机上搞状压DP的题。
思路
一个合法的构造需要包括所有的模式串，且一个模式串的前缀可能与另一个模式串的后缀相同，所以考虑搞个 $ AC $ 自动机。观察到数据量很小，且模式串个数只有 $ 8 $ 个，就会想到状压。
用一个二进制数 $ k $ 表示模式串的选择情况，第 $ i $ 位上为 $ 1 $ ，表示第 $ i $ 个串被选择了，反之没有。另一状态 $ i $ 是当前选到了第几位，仅凭这两个状态并不能知道下一位是否可以产生贡献，所以需要再加一个状态表示当前是在 $ Tire $ 树上节点编号为 $ j $ 的节点上。
为了加快转移的效率，我们预处理出 $ Tire$ 树上每个节点所包含的模式串信息，具体的：对于一个在节点 $ x $ 结束的模式串编号 $ i $ ，将 $ pos_{x} $ 或上 $ 1<<i $ ，表示当转移到节点 $ x $ 时，能提供一个模式串 $ i $ 。同时，该节点还需要包含其失配指针( $ nxt $ 数组)的所有信息，以做到 $ O(1) $ 的查询，所以对于 $ pos_{x} $ 还需要或上 $ pos_{nxt_{x}} $ 。
状态转移显然用刷表法舒服，令 $ v $ 为节点 $ j $ 通过 $ c $ 字符指向的儿子：
$ f_{i+1,v,k|pos_{v}}=f_{i+1,v,k|pos_{v}}+f{i,j,k} $ 。
记 $ Tire $ 树上的节点总个数为 $ cnt $ ， $ cnt \in [1,81] $ ，时间复杂度：$ O(L \cdot cnt \cdot 2^{n} \cdot 26 ) $ 。
code
code
#include <bits/stdc++.h>
#define i8 __int128
#define int long long
#define fuck inline
#define lb long double
using namespace std;
// typedef long long ll;
const int N=1e2+5,mod=998244353,S=70,M=2e6+5;
const int INF=1e9+7;
// const int inf=LONG_LONG_MAX/2;
// const int mod1=469762049,mod2=998244353,mod3=1004535809;
// const int G=3,Gi=332748118;
// const int M=mod1*mod2;
fuck int read()
{int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c-'0');c=getchar();}return x*f;
}
fuck void write(int x)
{if(x<0){putchar('-');x=-x;}if(x>9) write(x/10);putchar(x%10+'0');
}
int tr[N][30];
int nxt[N],pos[N];
string s[N];
int idx=0;
fuck void insert(string s,int x)
{int p=0;for(int i=0;i<s.size();i++){int frz=s[i]-'a';if(!tr[p][frz])tr[p][frz]=++idx;p=tr[p][frz];}pos[p]=(1<<x);
}
fuck void build()
{queue<int>q;for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<26;i++){int p=tr[u][i];if(p){nxt[p]=tr[nxt[u]][i];pos[p]|=pos[nxt[p]];q.push(p);}else tr[u][i]=tr[nxt[u]][i];}}
}
int n,l;
int f[N][N][(1<<9)+5];
fuck void solve()
{cin>>n>>l;for(int i=0;i<n;i++){string txt;cin>>txt;insert(txt,i);}build();f[0][0][0]=1;for(int i=0;i<l;i++)for(int j=0;j<=idx;j++)for(int k=0;k<(1<<n);k++)for(int c=0;c<26;c++){int v=tr[j][c];int frz=k|pos[v];f[i+1][v][frz]=(f[i+1][v][frz]+f[i][j][k])%mod;}int ans=0;for(int i=0;i<=idx;i++) ans=(ans+f[l][i][(1<<n)-1])%mod;cout<<ans<<"\n";
}
signed main()
{ // ios::sync_with_stdio(false); // cin.tie(0); cout.tie(0); // int QwQ=read();// int fuckccf=read();// while(QwQ--)solve(); solve(); return 0;
}
// 6666 66666 666666
// 6 6 6 6 6
// 6 6 6666 6
// 6 6 6 6 6
// 6666 6 6 6666666
完结收工！！！！！
个人主页
看完点赞，养成习惯
\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)