1030: [JSOI2007]文本生成器

https://www.lydsy.com/JudgeOnline/problem.php?id=1030

分析：

　　AC自动机+dp。

　　正难则反，求满足的，可以求出不满足的，用总的减去。所以考虑如何就出所有的长度为m的串里，没有出现任何一个单词的个数。

　　建立AC自动机，然后会有一些点是一定不能走的，这些点要么是某些单词的结尾，或者是包含了某些单词（以它结尾的串的后缀是一个单词）。

　　然后f[i][j]表示当前有i位，在AC自动机的第j个位置的方案数，即文本串中的后缀是AC自动机从0到这里构成的串，那么只要让文本串不要走有标记的点就行了。枚举下一位是什么，在AC自动机上转移。（注意，可能有许多点有些字符没有边，那么经过了这个字符也是合法的。这些的点贡献也要算上。假设存在这个点，直接转移即可。重新走到0号点的意义是当前和文本串的匹配长度为0）

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 #include<set>

 #include<vector>

 #include<queue>

 #include<map>

 #define fi(s) freopen(s,"r",stdin);

 #define fo(s) freopen(s,"w",stdout);

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 const int C = ;

 const int mod = ;

 char s[N];

 int f[N][C], ch[C][], val[C], fail[C], q[C], Index, n, m;

 void Insert(char *s) {

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

     for (int i=; i<=len; ++i) {

         int c = s[i] - 'A';

         if (!ch[u][c]) ch[u][c] = ++Index;

         u = ch[u][c];

     }

     val[u] = ;

 }

 void build() {

     int L = , R = ; fail[] = ;

     for (int c=; c<; ++c) {

         int u = ch[][c];

         if (u) fail[u] = , q[++R] = u;

     }

     while (L <= R) {

         int u = q[L ++];

         for (int c=; c<; ++c) {

             int v = ch[u][c];

             if (!v) {

                 ch[u][c] = ch[fail[u]][c]; continue; // !!!

             }

             q[++R] = v;

             int p = fail[u];

             while (p && !ch[p][c]) p = fail[p];

             fail[v] = ch[p][c];

             val[v] = val[v] ? val[v] : val[fail[v]];

         }

     }

 }

 void dp() {

     f[][] = ;

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

         for (int j=; j<=Index; ++j) {

             if (val[j] || !f[i][j]) continue;

             for (int c=; c<; ++c) { // 不仅要走存在的，也要走不存在的点，存在的点不能走有标记的。

                 (f[i + ][ch[j][c]] += f[i][j]) %= mod;

             }

         }

     }

 }

 int main() {

     n = read(), m = read();

     for (int i=; i<=n; ++i) {

         scanf("%s", s + );

         Insert(s);

     }

     build();

     dp();

     int ans = ;

     for (int i=; i<=m; ++i) ans = (ans * ) % mod;

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

         if (!val[j]) ans = (ans - f[m][j] + mod) % mod;

     cout << ans;

     return ;

 }

巴特西

1030: [JSOI2007]文本生成器

1030: [JSOI2007]文本生成器

最新文章

热门文章