BZOJ2553 [BeiJing2011]禁忌 【AC自动机 + dp + 矩乘优化】

时间：2024-10-16 16:37:38

题目链接

BZOJ2553

题解

话说在前，此题卡精度，最好开long double

先建\(AC\)自动机

求期望，逆着求，设\(f[i][j]\)为长度为\(i\)的串，当前匹配AC自动机\(j\)节点，之后能产生伤害的期望值

枚举转移，如果转移到一个单词节点，因为产生伤害的单词间不能相连，就直接跳回根节点

矩乘优化一下即可

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#include<cmath>

#include<iomanip>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 80,maxm = 100005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

char s[6][20];

int n,L,A,len[6];

int ch[maxn][26],fail[maxn],val[maxn],cnt;

void ins(int p){

	int u = 0,id;

	for (int i = 1; i <= len[p]; i++){

		id = s[p][i] - 'a';

		u = ch[u][id] ? ch[u][id] : (ch[u][id] = ++cnt);

	}

	val[u] = true;

}

void dfs(int u,int f){

	if (val[f]) val[u] = true;

	for (int i = 0; i < A; i++)

		if (ch[u][i]) dfs(ch[u][i],u);

}

void getf(){

	queue<int> q;

	for (int i = 0; i < A; i++) if (ch[0][i]) q.push(ch[0][i]);

	int u,v;

	while (!q.empty()){

		u = q.front(); q.pop();

		for (int i = 0; i < A; i++){

			v = ch[u][i];

			if (!v){

				ch[u][i] = ch[fail[u]][i];

				continue;

			}

			fail[v] = ch[fail[u]][i];

			q.push(v);

		}

	}

}

struct Matrix{

	long double s[maxn][maxn];

	int n,m;

	Matrix(){cls(s);n = m = 0;}

}C,F;

inline Matrix operator *(const Matrix& a,const Matrix b){

	Matrix c;

	if (a.m != b.n) return c;

	c.n = a.n; c.m = b.m;

	for (int i = 0; i < c.n; i++)

		for (int j = 0; j < c.m; j++)

			for (int k = 0; k < a.m; k++)

				c.s[i][j] += a.s[i][k] * b.s[k][j];

	return c;

}

inline Matrix qpow(Matrix a,int b){

	Matrix re; re.n = re.m = a.n;

	for (int i = 0; i < re.n; i++) re.s[i][i] = 1;

	for (; b; b >>= 1,a = a * a)

		if (b & 1) re = re * a;

	return re;

}

int main(){

	n = read(); L = read(); A = read();

	REP(i,n){

		scanf("%s",s[i] + 1),len[i] = strlen(s[i] + 1);

		ins(i);

	}

	dfs(0,0);

	getf();

	C.n = C.m = cnt + 2; long double x = 1.0 / A;

	for (int i = 0; i <= cnt; i++){

		if (val[i]) continue;

		for (int j = 0; j < A; j++){

			if (val[ch[i][j]]){

				C.s[i][cnt + 1] += x;

				C.s[i][0] += x;

			}

			else {

				C.s[i][ch[i][j]] += x;

			}

		}

	}

	C.s[cnt + 1][cnt + 1] = 1;

	F.n = cnt + 2; F.m = 1;

	F.s[cnt + 1][0] = 1;

	Matrix Fn = qpow(C,L) * F;

	long double ans = Fn.s[0][0];

	cout << fixed <<setprecision(12) << ans<<endl;

	return 0;

}

相关文章