BZOJ1030 [JSOI2007] 文本生成器

朱雀 2021-12-23 06:19 227阅读 0赞

我再看错模数我就是呆头

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

然后典型的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\n",(ksm(26,m)-dfs(rt,m)+mdn)%mdn);
    	return 0;
    }

转载于:https://www.cnblogs.com/hanyuweining/p/10321866.html