我再看错模数我就是呆头
考虑包含任意的补集不包含任何
然后典型的AC自动机上dp 长度为l不能走到任何关键点
特么模数多写了个0 问题是我刚跟zyf吐槽了模数
就当考前提醒了= =
//Love and Freedom.#include#include #include #include #include #define ll long long#define inf 20021225#define N 10100#define mdn 10007using namespace std;struct node{ int ch[26]; int fail; bool fn;}t[N];int cnt,rt,n,len;char ch[110];void insert(){ int pos = rt; for(int i=1;i<=len;i++) { int tmp = ch[i]-'A'; if(!t[pos].ch[tmp]) t[pos].ch[tmp] = ++cnt; pos = t[pos].ch[tmp]; } t[pos].fn = 1;}queue q;void getfail(){ for(int i=0;i<26;i++) if(t[rt].ch[i]) t[t[rt].ch[i]].fail = rt,q.push(t[rt].ch[i]); else t[rt].ch[i] = rt; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0;i<26;i++) if(t[x].ch[i]) { int s = t[x].ch[i]; t[s].fail = t[t[x].fail].ch[i]; if(t[t[s].fail].fn) t[s].fn = 1; q.push(s); } else { t[x].ch[i] = t[t[x].fail].ch[i]; } }}int f[N][110];int dfs(int x,int l){ if(!l) return 1; if(~f[x][l]) return f[x][l]; f[x][l] = 0; for(int i=0;i<26;i++) if(!t[t[x].ch[i]].fn) f[x][l] = (f[x][l] + dfs(t[x].ch[i],l-1))%mdn; return f[x][l];}int ksm(int bs,int mi){ int ans = 1; while(mi) { if(mi&1) ans = ans*bs%mdn; bs=bs*bs%mdn; mi>>=1; } return ans;}int main(){ int m; memset(f,-1,sizeof(f)); scanf("%d%d",&n,&m); rt = cnt = 1; for(int i=1;i<=n;i++) { scanf("%s",ch+1); len = strlen(ch+1); insert(); } getfail(); printf("%d\n",(ksm(26,m)-dfs(rt,m)+mdn)%mdn); return 0;}