【题目链接】

https://loj.ac/problem/10063

【题意】

给出长度为m，n个模式串，请问只要长度为m的串中有一个模式串就算是可读。

【分析】

其实如果直接分析全部可读的情况，一个串，两个串，……n个串可读。

明显是很复杂而且是做不出来的。

正难则反，其实我们可以需要通过一个（所有可能-全部不可读的情况）不就是答案的方案吗？

记录不合法的方案，考虑dp[i][j] ，下标为j，长度为i 的不可读的情况。

其实不可读的情况就是不经过结尾的结点即可。

最后答案就是利用26个字母，然后子节点通过父节点来累加答案。

最后把对立事件算出来即可。

#include
#include
#include
#include

using namespace std;
const int N = ;
const int M = 2e6+;
const int mod = ;
int Trie[M][] , fail[M] , End[M], idx ;
int Q[M] , Head , Tail ;
int f[N][N];
int n ,m ;

char str[N];

void Insert( char s[] ){
int p = ;
for(int i= ; s[i] ; i++ ){
int t = s[i] - 'A' ;
if( !Trie[p][t] )
Trie[p][t] = ++idx ;
p = Trie[p][t];
}
End[p] |= ;
}

void Build(){
Head = , Tail = ;
for(int i=;i<;i++)
if(Trie[][i])
Q[++Tail] = Trie[][i] ;

 while( Head <= Tail ){  
     int u = Q\[Head++\] ;  
     for(int i=;i<;i++){  
         int To = Trie\[u\]\[i\];  
         if( To ){  
             fail\[To\] = Trie\[fail\[u\]\]\[i\];  
             Q\[++Tail\] = To;

             End\[To\] |= End\[fail\[To\]\] ;  
         }else{  
             Trie\[u\]\[i\] = Trie\[fail\[u\]\]\[i\];  
         }  
     }  
 }

}

void Solve(){
f[][] = ;
for(int i=;i<=m;i++){ for(int j=;j<=idx;j++){ for(int k=;k<;k++){ int To = Trie[j][k]; if( !End[To] ){ (f[i][To] += f[i-][j]) %= mod ; } } } } int tot = ; for(int i=;i<=idx;i++){ tot = (tot+f[m][i]) % mod ; } int sum = ; for(int i=;i<=m;i++){ sum = sum * % mod ; } printf("%d\n",(sum-tot+mod)%mod ); } int main() { ios_base :: sync_with_stdio(false); cin.tie() , cout.tie(); cin >> n >> m ;
for(int i=;i> str ;
Insert(str);
}
Build();
Solve();
return ;
}