题目链接

题意

给出(n)个字符串，要构造一个长度为(m)的字符串(s)，使得给出的(n)个字符串中至少有一个是(s)的子串。问方案数。

思路

(ac)自动机+(dp)
考虑至少有一个是s的子串不好考虑。考虑用全部情况减去其中不包含任何一个字符串的情况。
全部情况就是(26^m)，然后考虑怎么求出不包含任何一个字符串的情况。
用(f[i][j])表示已经确定了(i)个字符，现在到了(ac)自动机的j位置的方案数。
显然如果(j)位置是给出字符串的结尾或者沿着(fail)指针可以跳到给出字符串的结尾，那么就不能转移。其他的就可以转移到(f[i + 1][k])。(k)是(j)在(ac)自动机上的一个儿子。
最后答案就是(26^m-sumlimits_{i = 0}^{tot}f[m][i](i不是给出字符串的结尾))

代码

/* * @author: wxyww * @date:   2019-02-01 19:33:15 * @last modified time: 2019-02-01 20:04:44 */ #include<cstring> #include<queue> #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> using namespace std; typedef long long ll; const int n = 6000 + 10,mod = 10007; ll read() {     ll 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*10+c-'0';         c=getchar();     }     return x*f; } char s[110]; queue<int>q; int trie[n][27],bz[n],fail[n],tot; void ins() {     int len = strlen(s + 1);     int now = 0;     for(int i = 1;i <= len;++i) {         int x = s[i] - 'a';         if(!trie[now][x]) trie[now][x] = ++tot;         now = trie[now][x];     }     bz[now] = 1; } void get_fail() {     for(int i = 0;i < 26;++i) if(trie[0][i]) q.push(trie[0][i]);     while(!q.empty()) {         int u = q.front();q.pop();         bz[u] |= bz[fail[u]];         for(int i = 0;i < 26;++i) {             if(trie[u][i]) fail[trie[u][i]] = trie[fail[u]][i],q.push(trie[u][i]);             else trie[u][i] = trie[fail[u]][i];         }     } } int qm(int x,int y) {     int ans = 1;     for(;y;y >>= 1,x = 1ll * x * x % mod) {         if(y & 1) ans = 1ll * ans * x % mod;     }     return ans; } int f[n][n]; int main() {     int n = read(),m = read();     for(int i = 1;i <= n;++i) {         scanf("%s",s + 1);         ins();     }     get_fail();     f[0][0] = 1;      for(int i = 0;i < m;++i) {         for(int j = 0;j <= tot;++j) {             if(bz[j] || !f[i][j]) continue;             for(int k = 0;k < 26;++k) {                 int z = trie[j][k];                 f[i + 1][z] += f[i][j];                 f[i + 1][z] >= mod ? f[i + 1][z] -= mod : 0;             }         }     }     int ans = qm(26,m);     for(int i = 0;i <= tot;++i) {         if(!bz[i]) ans = (ans - f[m][i] + mod) % mod;     }     cout<<ans;     return 0; }