好像是入门题的说
跑生成的串中不带给定字符串的个数ans 26^m-ans就是答案
dp[i][j]表示字符第i位在ac自动机上第j的节点的合法情况数
如果转移到的下一个节点是字符的结尾，就是非法的
转移dp[i][j]+=dp[i-1][j];
ps 节点编号从1开始
#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> #include<set> #include<map> #include<vector> #define inf 0x3f3f3f3f #define mem(a,b) memset(a,b,sizeof(a)) #define ll long long #define sd(x) scanf("%d",&(x)) #define sl(x) scanf("%lld",&(x)) #define scs(s) scanf("%s",s) #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) #define lowbit(x) x&(-x) using namespace std; const int maxn=1e5+10; const int mod=10007; int dp[105][6005]; int mub=1; int tree[maxn][26],cnt[maxn]; int fail[maxn],End[maxn][26]; char s[maxn]; void Insert() { int root=1; int l=strlen(s); rep(i,0,l-1) { int now=s[i]-'A'; if(!tree[root][now]) tree[root][now]=++mub; root=tree[root][now]; } cnt[root]++; } void getfail() { for(int i=1;i<=mub;i++) fail[i]=1; queue<int>q;fail[1]=0; q.push(1); while(!q.empty()) { int now=q.front(); q.pop(); rep(i,0,25) { int k=fail[now]; if(tree[now][i]) { q.push(tree[now][i]); fail[tree[now][i]]=k?tree[fail[now]][i]:1; cnt[tree[now][i]]|=cnt[fail[tree[now][i]]]; } else tree[now][i]=k?tree[fail[now]][i]:1; } } } void DP(int x) { rep(i,1,mub) { rep(j,0,25) { if(cnt[tree[i][j]]) continue; dp[x][tree[i][j]]+=dp[x-1][i]; dp[x][tree[i][j]]%=mod; } } } int main(){ int n,m,ans=1,tot=0; sd(n),sd(m); rep(i,1,n) scs(s),Insert(); getfail();dp[0][1]=1; rep(i,1,m) DP(i),ans=(ans*26)%mod; rep(i,1,mub) tot=(tot+dp[m][i])%mod; printf("%d ",((ans-tot)%mod+mod)%mod); return 0; }