BZOJ 2553 BeiJing2011 禁忌 AC自動機+矩陣乘法

題目大意：給定n個模式串，定義一個字符串的傷害為所有子串的劃分中最多包含的模式串數量，求長度為len的字符串的傷害期望值

小五prpr，戀戀prpr，大小姐prpr

首先建立AC自動機 令f[i][j]表示長度為i的字符串在AC自動機上的第j個節點的傷害期望值

如果要走到某個節點是危險節點或者fail指針指向危險節點，就ans++，然後回到根節點

這樣構造出來的矩陣做快速冪= = 這麼做都會把- - 不會別罵我- -

但是跑完發現找不到答案- - 因此我們需要稍微改造一下- -

新建一個節點 如果某個節點因為危險返回了根 就同時向該節點連一條邊

新節點的唯一一條出邊邊權為1指向自己- - 這樣搞出來的鄰接矩陣自乘len次，得到的矩陣的[root][new_node]就是答案- -

相當於把AC自動機看成一個圖 去圖上求根到新節點走恰好len步的期望值

好題- - 注意開long double不然卡精- - 雖說如此總比那些用double去卡long double精度的題強- -

大半夜的我寫的是啥自己都看不懂了- - 沒看懂的地方去看代碼吧但願寫的還能清晰點。。。 吧。。。

#include 
#include 
#include 
#include 
#include 
#define M 110
using namespace std;
int n,len,alphabet;
char s[M];
namespace Aho_Corasick_Automaton{
	struct Trie{
		Trie *son[26],*fail;
		bool ed;
	}mempool[M],*C=mempool,*root;
	void Insert(Trie* &p,char *s)
	{
		if(!p) p=C++;
		if(!*s)
		{
			p->ed=1;
			return ;
		}
		Insert(p->son[(*s)-'a'],s+1);
	}
	void Build_Tree()
	{
		static Trie *q[M];
		int i,r=0,h=0;
		for(i=0;i<26;i++)
			if(root->son[i])
				(q[++r]=root->son[i])->fail=root;
			else
				root->son[i]=root;
		while(r!=h)
		{
			Trie *p=q[++h];
			for(i=0;i<26;i++)
				if(p->son[i])
				{
					p->son[i]->fail=p->fail->son[i];
					p->son[i]->ed|=p->fail->son[i]->ed;
					q[++r]=p->son[i];
				}
				else
					p->son[i]=p->fail->son[i];
		}
	}
}
namespace Matrix_Multiplication{
	int size;
	struct Matrix{
		long double memory[M][M];
		Matrix()
		{
			memset(memory,0,sizeof memory);
		}
		long double* operator [] (int x)
		{
			return memory[x];
		}
		friend void operator *= (Matrix &x,Matrix &y)
		{
			int i,j,k;
			Matrix z;
			for(i=0;i<=size;i++)
				for(j=0;j<=size;j++)
					for(k=0;k<=size;k++)
						z[i][j]+=x[i][k]*y[k][j];
			x=z;
		}
	}f;
	Matrix Quick_Power(Matrix x,int y)
	{
		Matrix re;
		for(int i=0;i<=size;i++)
			re[i][i]=1;
		while(y)
		{
			if(y&1) re*=x;
			x*=x;y>>=1;
		}
		return re;
	}
}
int main()
{
	using namespace Aho_Corasick_Automaton;
	using namespace Matrix_Multiplication;
	int i,j;
	cin>>n>>len>>alphabet;
	for(i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		Insert(root,s+1);
	}
	Build_Tree();
	size=C-mempool;
	long double temp=1.0/alphabet;
	for(j=0;j