洛谷 4052 libreoj 10063 bzoj 1030 [JSOI2007]文本生成器 题解

发表于 | 更新于 | 阅读次数：
本文字数： 651 字 | 阅读时长 ≈ 3 分钟

题意简述

你要求有多少个字符串，使得：

  1. 长度为m
  2. 包含至少一个给定的单词。会给定个单词。

膜

思路框架

用总共的方案数减去一个单词都不包含的方案数。前面那个是，后面那个在自动机上跑求解。

具体思路

首先，“至少一个”->“总共减去一个都没有”，是一个经典套路。这个不多说。

然后讲讲如何。设表示，长度为，匹配到自动机的第个位置。在建立然后若合法，那么就从转移到。最后的答案是所有的和。

实现注意

  1. AC自动机别写挂了
  2. 多开点空间，别怂

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 14444
	#define mod 10007
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)

	bool cxk[N];
	class Ah_Chtholly_Automaton
	{
	public:
		int tr[N][26];
		int tot;
		void Init()
		{
			FK(tr);
			tot=0;
		}
		int Insert(char s[])
		{
			int pos=0;
			for(int i=0;s[i];++i)
			{
				int c=s[i]-'A';
				if (!tr[pos][c])
				{
					tr[pos][c]=++tot;
				}
				pos=tr[pos][c];
			}
			cxk[pos]=1;
			return pos;
		}

		int fail[N];
		queue<int> Q;
		void BuildFail()
		{
			FK(fail);
			while(!Q.empty()) Q.pop();

			F(i,0,25) 
			{
				if (tr[0][i]) Q.push(tr[0][i]);
			}
			while(!Q.empty())
			{
				int u=Q.front();Q.pop();

				F(i,0,25)
				{
					if (tr[u][i])
					{
						fail[tr[u][i]]=tr[fail[u]][i];
						cxk[tr[u][i]]|=cxk[fail[tr[u][i]]];
                                                //是否合法的判断：如果fail不合法，那我也不合法
						Q.push(tr[u][i]);
					}
					else tr[u][i]=tr[fail[u]][i];
				}
			}
		}
	}AC;

	int n,m;
	int id[N];
	char tmp[N];
	void Input()
	{
		scanf("%d%d",&n,&m);
		AC.Init();
		F(i,1,n)
		{
			scanf("%s",tmp);
			id[i]=AC.Insert(tmp);
		}
	}

	int dp[110][N];
	int qpow(int a,int b,int m)
	{
		int r=1;
		while(b)
		{
			if (b&1) r=r*a%m;
			a=a*a%m,b>>=1;
		}
		return r;
	}
	void Soviet()
	{
		AC.BuildFail();
		dp[0][0]=1;
		F(i,0,m-1) F(j,0,AC.tot) F(k,0,25)
		{
			int ch=AC.tr[j][k];
			if (!cxk[ch])
			{
				dp[i+1][ch]+=dp[i][j];
				dp[i+1][ch]%=mod;
			}
		}

		int ans=qpow(26,m,mod);
		F(i,0,AC.tot) 
		{
			ans=(ans-dp[m][i]+mod)%mod;
		}
		printf("%d\n",ans);	
	}
	void IsMyWife()
	{
		Input();
		Soviet();
	}
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}
w