【BZOJ1030】[JSOI2007] 文本生成器（AC自动机上跑DP）

点此看题面

大致题意： 给你\(N\)个字符串（只含大写字母），要你求出有多少个由\(M\)个大写字母构成的字符串含有这\(N\)个字符串中的至少一个。

\(AC\)自动机

看到题目，应该比较容易想到用\(AC\)自动机去做。

但是，即使用了\(AC\)自动机，这题直接求还是很麻烦，所以我们需要将题意先转化一下。

题意转化

考虑对于一个由\(M\)个大写字母构成的字符串，无非有两种情况：

第一种情况： 这个字符串中含有这\(N\)个字符串中的至少一个。
第二种情况： 这个字符串中不含这\(N\)个字符串中的任意一个。

题目中让我们求的是第一种情况的方案数，但是，第二种情况的方案数显然更好搞。

因此，我们只需求出第二种情况的方案数，再用总方案数\(26^M\)减去它，就是第一种情况的方案数了。

那么第二种情况的方案数怎么求呢？就需要用上\(DP\)了。

动态规划

考虑用\(f_{i,j}\)来表示一共由\(i\)个大写字母构成，最后到达\(Trie\)上第\(j\)个节点的字符串中不含\(N\)个字符串中任意一个字符串的方案数。

初始化时，对于每一个不为这\(N\)个字符串中任意一个字符串的结尾的节点\(i\)，\(f_{0,i}=1\)

那么状态转移方程应为：

\[f_{i,j}=\sum_{k=0}^{25} f_{i-1,node[j].Son[k]}
\]

最后，\(f_{m,rt}\)即为第二种情况的方案数。

因此，最后答案就是\(26^M-f_{m,rt}\)，至于\(26^M\)要不要用快速幂来优化，那随你便吧（反正我是写了）。

写的过程中还有一些小细节可以优化，这里就不多说了，直接上代码吧。

代码

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define LL long long

#define ull unsigned long long

#define swap(x,y) (x^=y,y^=x,x^=y)

#define tc() (A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++)

#define pc(ch) (pp_<100000?pp[pp_++]=ch:(fwrite(pp,1,100000,stdout),pp[(pp_=0)++]=ch))

#define M 100

#define SUM 6000

#define MOD 10007

int pp_;char ff[100000],*A=ff,*B=ff,pp[100000];

using namespace std;

int n,m,f[M+5][SUM+5];//f[i][j]表示一共由i个大写字母构成，最后到达Trie上第j个节点的字符串中不含n个字符串中任意一个字符串的方案数

namespace AC_Automation//AC自动机

{

	int rt=1,tot=1;

	struct Trie

	{

    	int Son[26],Next,Cnt;

	}node[SUM+5];

	queue<int> q;

	inline void Insert(string st)//将一个字符串st插入Trie中

	{

    	register int i,nxt,x=rt,len=st.length();

    	for(i=0;i<len;++i)

    	{

        	if(!node[x].Son[nxt=st[i]-65]) node[x].Son[nxt]=++tot;

        	x=node[x].Son[nxt];

    	}

    	++node[x].Cnt;//统计这一个节点是否有字符串

	}

	inline void GetNext()//求失配指针

	{

    	register int i,k;q.push(rt);

    	while(!q.empty())

    	{

        	k=q.front(),q.pop();

        	for(i=0;i<26;++i)

        	{

            	if(k^rt)

            	{

                	if(!node[k].Son[i]) node[k].Son[i]=node[node[k].Next].Son[i];

                	else node[node[k].Son[i]].Next=node[node[k].Next].Son[i],node[node[k].Son[i]].Cnt|=node[node[node[k].Son[i]].Next].Cnt,q.push(node[k].Son[i]);

            	}

            	else

            	{

                	if(!node[k].Son[i]) node[k].Son[i]=rt;

                	else node[node[k].Son[i]].Next=rt,q.push(node[k].Son[i]);

            	}

        	}

    	}

	}

	inline int GetAns()//求答案

	{

		register int i,j,k;

		for(GetNext(),i=1;i<=tot;++i)

			if(!node[i].Cnt) f[0][i]=1;//初始化每个不是n个字符串中某一字符串结尾的节点f[0][i]=1

		for(i=1;i<=m;++i)//DP的核心代码

			for(j=1;j<=tot;++j)

				for(k=0;k<26;++k)//枚举第j个节点的每一个儿子

					if(!node[j].Cnt) (f[i][j]+=f[i-1][node[j].Son[k]])%=MOD;//若i不是n个字符串中某一字符串结尾的节点，则计算f[i][j]

		register int res=1,x=26,p=m;//快速幂（写不写无所谓，写了也比O(m)求快不了多少）

		while(p)

		{

			if(p&1) (res*=x)%=MOD;

			(x*=x)%=MOD,p>>=1;

		}

		return ((res-f[m][rt])%MOD+MOD)%MOD;//两数相减后可能为负，因此要加上一个MOD

	}

};

inline void read(int &x)

{

	x=0;static char ch;

	while(!isdigit(ch=tc()));

	while(x=(x<<3)+(x<<1)+ch-48,isdigit(ch=tc()));

}

inline void read_string(string &x)

{

	x="";static char ch;

	while(isspace(ch=tc()));

	while(x+=ch,!isspace(ch=tc())) if(!(~ch)) return;

}

inline void write(int x)

{

	if(x>9) write(x/10);

	pc(x%10+'0');

}

int main()

{

	register int i,j;register string ss;

	for(read(n),read(m),i=1;i<=n;++i) read_string(ss),AC_Automation::Insert(ss);//将n个字符串插入Trie中

	return write(AC_Automation::GetAns()),fwrite(pp,1,pp_,stdout),0;//输出答案

}

巴特西

【BZOJ1030】[JSOI2007] 文本生成器（AC自动机上跑DP）

\(AC\)自动机

题意转化

动态规划

代码

最新文章

热门文章