注意到串长<=50 没有取模 先跑遍AC自动机建出trie图 构造出邻接矩阵后可以用DP+高精解决
s( i , j )代表矩阵第 i 行第 j 列(从节点i到节点j的安全方案数量) f( k , i )代表长度为 k ,当前在节点 i 的可行串的数量 f( k+1 , j ) += f( k , j ) * s( i , j )
答案即为 f( m , 1 ) + f( m , 2 ) + …. f( m , cnt )
#include <cstdio>#include <algorithm>#include <cstring>#include <queue>#include <map>#define MAXN 105using namespace std;int n,m,p;int s[MAXN][MAXN],f[MAXN][55][105],ans[105];char a[MAXN];map<char,int> mp;struct trie{ int cnt,root; int nx[MAXN][55],fail[MAXN]; bool end[MAXN]; int newnode() { cnt++; for(int i=0;i<n;i++) nx[cnt][i]=0; fail[cnt]=end[cnt]=0; return cnt; } void init() { cnt=0; root=newnode(); } void insert(char *s) { int len=strlen(s),now=root; for(int i=0;i<len;i++) { if(!nx[now][mp[s[i]]]) nx[now][mp[s[i]]]=newnode(); now=nx[now][mp[s[i]]]; } end[now]=1; } void build_fail() { queue<int> q; for(int i=0;i<n;i++) { if(!nx[root][i]) nx[root][i]=root; else fail[nx[root][i]]=root,q.push(nx[root][i]); } while(!q.empty()) { int now=q.front(); if(end[fail[now]]) end[now]=1; for(int i=0;i<n;i++) { if(nx[now][i]) { fail[nx[now][i]]=nx[fail[now]][i]; q.push(nx[now][i]); } else nx[now][i]=nx[fail[now]][i]; } q.pop(); } return; } void get_mat() { for(int i=1;i<=cnt;i++) { if(end[i]) continue; for(int j=0;j<n;j++) if(!end[nx[i][j]]) s[i][nx[i][j]]++; } }}AC;void add(int *a,int *b,int t){ if(!t) return; for(int i=1;i<=100;i++) a[i]+=b[i]*t; for(int i=1;i<=100;i++) { a[i+1]+=a[i]/10; a[i]%=10; }}void PRint(){ int j=100; while(!ans[j]&&j>0) j--; if(!j) printf("0/n"); for(;j;j--) printf("%d",ans[j]); printf("/n");}void dp(){ memset(f,0,sizeof(f)); f[1][0][1]=1; for(int k=0;k<m;k++) for(int i=1;i<=AC.cnt;i++) for(int j=1;j<=AC.cnt;j++) add(f[j][k+1],f[i][k],s[i][j]); memset(ans,0,sizeof(ans)); for(int i=1;i<=AC.cnt;i++) add(ans,f[i][m],1);}int main(){ while(scanf("%d%d%d",&n,&m,&p)!=EOF) { AC.init(); scanf("%s",a); for(int i=0;i<n;i++) mp[a[i]]=i; for(int i=1;i<=p;i++) { scanf("%s",a); AC.insert(a); } AC.build_fail(); AC.get_mat(); dp(),print(); } return 0;}新闻热点
疑难解答
