AC自动机
考虑一位一位填字符
一旦包含了单词（即经过了结束标记或fail上的结束标记）
那么后面不管填什么都是一篇可读的文章
如果一共要填 m 个单词，当前填到了第 i 个字符就一定可读了
那么后面每个字符都有 26 种填法，所以方案就多了 26^(m-i) 种
然后打了个 30 分的搜索
在AC自动机上走，一旦有匹配就更新答案，不用再下去搜，返回找其他方案
其他TLE
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; const int mo=10007; const int N=1e5+7; int n,m,ans; int c[N][27],fail[N],cnt; bool pd[N]; char a[N]; inline void ins() { int u=0,len=strlen(a); for(int i=0;i<len;i++) { int v=a[i]-'A'+1; if(!c[u][v]) c[u][v]=++cnt; u=c[u][v]; } pd[u]=1; } queue <int> qa; inline void pre() { for(int i=1;i<=26;i++) if(c[0][i]) qa.push(c[0][i]); while(!qa.empty()) { int u=qa.front(); qa.pop(); for(int i=1;i<=26;i++) { int v=c[u][i]; if(!v) c[u][i]=c[fail[u]][i]; else { fail[v]=c[fail[u]][i]; pd[v]|=pd[fail[v]];//只要fail上有结束标记，当前节点也包含可读单词 qa.push(v); } } } } inline int ksm(int x) { int res=1,a=26; while(x) { if(x&1) res=res*a%mo; a=a*a%mo; x>>=1; } return res; } void dfs(int stp,int pos)//已经填了stp个单词,当前在自动机的pos位置上 { if(pd[pos])//如果包含可读单词直接更新答案并返回 { ans=(ans+ksm(m-stp))%mo; return; } if(stp==m) return;//边界 for(int i=1;i<=26;i++) { int v=c[pos][i]; dfs(stp+1,v);//向下填单词 } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { scanf("%s",a); ins(); } pre(); dfs(0,0); cout<<ans; return 0; }
考虑把搜索换成DP
设 f[ i ] [ j ] 表示填了第 i 个单词，当前在AC自动机的 j 位置上有几种方案
转移显然，f[ i+1 ] [ k ] += f [ i ] [ j ] ( j 可以走到 k )
如果 j 有包含可读单词，那么 ans += f[ i ] [ j ] * 26^(m-i)，并且这个状态不用转移到后面的状态
然后是代码
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; const int mo=10007; const int N=1e5+7; int n,m,ans; int c[N][27],fail[N],cnt; bool pd[N]; char a[N]; inline void ins() { int u=0,len=strlen(a); for(int i=0;i<len;i++) { int v=a[i]-'A'+1; if(!c[u][v]) c[u][v]=++cnt; u=c[u][v]; } pd[u]=1; } queue <int> qa; inline void pre() { for(int i=1;i<=26;i++) if(c[0][i]) qa.push(c[0][i]); while(!qa.empty()) { int u=qa.front(); qa.pop(); for(int i=1;i<=26;i++) { int v=c[u][i]; if(!v) c[u][i]=c[fail[u]][i]; else { fail[v]=c[fail[u]][i]; pd[v]|=pd[fail[v]];//只要fail上有结束标记，当前也包含可读单词 qa.push(v); } } } } inline int ksm(int x) { int res=1,a=26; while(x) { if(x&1) res=res*a%mo; a=a*a%mo; x>>=1; } return res; } int f[107][N]; void slove() { for(int i=1;i<=26;i++) f[1][c[0][i]]++;//初始状态 for(int i=1;i<=m;i++)//填第i位 { for(int j=0;j<=cnt;j++)//在自动机上的第j个位置 { if(!f[i][j]) continue; if(pd[j])//如果有包含单词 { ans=(ans+f[i][j]*ksm(m-i)%mo)%mo;//更新答案 continue; } for(int k=1;k<=26;k++)//负责把状态向下一步转移 { int v=c[j][k]; f[i+1][v]=(f[i+1][v]+f[i][j])%mo; } } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { scanf("%s",a); ins(); } pre(); slove(); cout<<ans; return 0; }