BZOJ2553 [BeiJing2011]禁忌

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int n,len,bet;

struct Matrix{
	int n,m;
	long double a[105][105];

	void Init() {
		n=m=0;
		memset(a,0,sizeof(a));
	}
}E;

Matrix operator * (Matrix x,Matrix y) {
	Matrix z; z.Init();
	z.n=x.n; z.m=y.m;
	for (int i=0;i<=z.n;i++) {
		for (int j=0;j<=z.m;j++) {
			for (int k=0;k<=x.m;k++) {
				z.a[i][j]+=x.a[i][k]*y.a[k][j];
			}
		}
	}
	return z;
}

namespace AC {
	char s[N];
	int rt=0,tot=0;
	int ch[N][26],tag[N],fail[N];

	void insert() {
		scanf("%s",s+1); int l=strlen(s+1);
		int now=rt;
		for (int i=1;i<=l;i++) {
			if (tag[now]) return;
			if (!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++tot;
			now=ch[now][s[i]-'a'];
		}
		tag[now]=1;
	}

	void Getfail() {
		queue<int> Q;
		fail[rt]=rt;
		for (int i=0;i<bet;i++) {
			if (ch[rt][i]) fail[ch[rt][i]]=rt,Q.push(ch[rt][i]);
		}
		while (!Q.empty()) {
			int x=Q.front(); Q.pop();
			for (int i=0;i<bet;i++) {
				if (ch[x][i]) {
					fail[ch[x][i]]=ch[fail[x]][i];
					Q.push(ch[x][i]);
				}
				else ch[x][i]=ch[fail[x]][i];
			}
		}
	}
}
using namespace AC;

int main() {
	scanf("%d%d%d",&n,&len,&bet);
	for (int i=1;i<=n;i++) insert();
	Getfail();
	E.n=E.m=tot;
	E.a[tot][tot]=1.0;
	for (int i=0;i<tot;i++) {
		for (int j=0;j<bet;j++) {
			if (tag[ch[i][j]]) {
				E.a[i][rt]+=1.0/bet;
				E.a[i][tot]+=1.0/bet;
			}
			else E.a[i][ch[i][j]]+=1.0/bet;
		}
	}
	Matrix ans; ans.Init();
	ans.n=ans.m=tot;
	for (int i=0;i<=tot;i++) ans.a[i][i]=1;
	while (len) {
		if (len&1) ans=ans*E;
		E=E*E; len>>=1;
	}
	printf("%.10Lf",ans.a[0][tot]);
	return 0;
}