BZOJ1030 [JSOI2007] 文本生成器

我再看错模数我就是呆头

考虑包含任意的补集不包含任何

然后典型的AC自动机上dp 长度为l不能走到任何关键点

特么模数多写了个0 问题是我刚跟zyf吐槽了模数

就当考前提醒了= =

//Love and Freedom.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
#define inf 20021225
#define N 10100
#define mdn 10007
using 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<int> 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
",(ksm(26,m)-dfs(rt,m)+mdn)%mdn);
	return 0;
}