P6125 [JSOI2009]有趣的游戏 && P3706 [SDOI2017]硬币游戏

显然有用的状态只有那些在AC自动机上匹配的状态

然后我们设 $f_i$ 表示AC自动机上节点i经过期望次数

转移考虑直接向下一个节点走过去即可

根据这些边我们能建立nm个方程然后高斯消元

注意我们一号点要钦定多1次经过次数!

然后我们应该还是可以用概率做的,但是昨天尝试了一下发现不太对啊

应该是和状态转移冲突了....

注意fail树上有end的节点不能向下走啊


//AC 自动机暴力即可
//如果要n^3我也不拦着你
#include<bits/stdc++.h>
#define db double
using namespace std;
const int MAXN = 400;
const int MAXM = 400;
int n, l, m, T;
int p[MAXN], q[MAXN], ch[MAXM][MAXN], siz[MAXM], ed[MAXM];
char s[MAXN];

inline void ins(char *s, int x) {
	int n = strlen(s);
	int u = 0;
 	for(int i = 0; i < n; ++i) {
		int t = s[i] - 'A';
		if(!ch[u][t])ch[u][t] = ++T;
		u = ch[u][t]; 
 	}
 	siz[u] = 1;//这个是end节点呢!
	ed[x] = u;
	return ;
}

int que[MAXM], fail[MAXM];
inline void init() {
	int hd = 1, tl = 0;
	for(int i = 0; i < m; ++i) {
		if(ch[0][i]) {
			que[++tl] = ch[0][i];//这些节点直接指父亲??
			fail[ch[0][i]] = 0;
		}
	}
	while(hd <= tl) {
		int u = que[hd];
		hd++;
		siz[u] |= siz[fail[u]];
		for(int i = 0; i < m; ++i) {
			if(ch[u][i]) {
				fail[ch[u][i]] = ch[fail[u]][i];
				que[++tl] = ch[u][i];
			} else {
				ch[u][i] = ch[fail[u]][i];
			}
		}
	}
 	return ;
}

db a[MAXN][MAXN];

inline void out() {
	for(int u = 0; u <= T; ++u) {
		for(int j = 0; j <= T + 1; ++j) {
			printf("%.2lf ", a[u][j]);
		}
		puts("");
	}
	puts("\n");
}

const db eps = 1e-10;
inline void guass() {
	for(int i = 0; i <= T; ++i) {
		int t = i + 1;
		while(t <= T && fabs(a[t][i]) <= fabs(a[i][i]))
			++t;
		if(t != i && t <= T) {
			for(int j = 0; j <= T + 1; ++j) {
				swap(a[t][j], a[i][j]);
			}
		}
		db kk = a[i][i];
		for(int j = 0; j <= T + 1; ++j)a[i][j] /= kk;
		for(int j = 0; j <= T; ++j) {
			if(i == j)continue;
			db kk = a[j][i];
			for(int k = 0; k <= T + 1; ++k) {
				a[j][k] = a[j][k] - a[i][k] * kk;
			}
		}
 	}
 	return;
}

//建立方程吧?....
inline void solve() {
	//设立这个方程吧
	a[0][T + 1] = 1;
	for(int u = 0; u <= T; ++u) {
		a[u][u] += 1;
		if(siz[u])continue;
		for(int i = 0; i < m; ++i) {
			a[ch[u][i]][u] -= p[i] / (db)q[i];
		}
	}
 	guass();
	for(int i = 1; i <= n; ++i) {
		printf("%.2lf\n", a[ed[i]][T + 1]);
	}
	return ;
}

int main() {
	scanf("%d%d%d", &n, &l, &m);
	for(int i = 0; i < m; ++i) {
		scanf("%d%d", &p[i], &q[i]);
	}
	for(int i = 1; i <= n; ++i) {
		scanf("%s", s);
		ins(s, i);
	}
	init();
	solve();
	return 0;
}

关于fail树上传标记一事:

对于u,v两个点,u->v,所以我们v不一定有u的fail上信息,因为我们一旦走到v,就一定走过了u,已经有了u的信息

直接从根走到v

那显然经过了u

走fail跳到了v

你会发现这样一定存在一个节点的fail指向u,而你走过了那个节点!

举例:

abcdefghijk

e~h ->v

e~f -> u

a~h -> v'

a~f -> u'

v'有fail指向v,u'有fail直到u

但是如果你走到v'所以一定会经过这个u',而u'得到了u的信息!!

P3706 [SDOI2017]硬币游戏

这道题的题解在生成函数进阶里面有,不过我单独分一栏出来吧!

注意!!double虽然很容易爆精度,但是有效数字有14位,所以是没事情的

而且一定要写:用绝对值最大的主元来消的写法,否则就会自闭,你eps写个1e-300?


#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const int MAXN = 400;
const ll bas = 12345;
const int P = 998244353;

db a[MAXN][MAXN];
long db inv[MAXN];
int n, m, b[MAXN][MAXN];
char s[MAXN];
ll hsh[MAXN][MAXN], hsh2[MAXN][MAXN], B[MAXN];

inline void init() {
	B[0] = 1;
	for(int i = 1; i <= m; ++i)B[i] = B[i - 1] * bas % P;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			hsh[i][j] = hsh[i][j - 1] * bas % P + b[i][j];
			hsh[i][j] %= P;
			// printf("%d %d %lld\n", i, j, hsh[i][j]);
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = m; j >= 1; --j) {
			hsh2[i][j] = hsh2[i][j + 1] + b[i][j] * B[m - j] % P;
			hsh2[i][j] %= P;
			// printf("%d %d %lld\n", i, j, hsh2[i][j]);
		}
	}
	inv[0] = 1;
	for(int i = 1; i <= m; ++i) {
		inv[i] = inv[i - 1] * 0.5;
	}
	return;
}

inline void out(int n) {
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n + 1; ++j) {
			printf("%.6lf ", a[i][j]);
		}
		puts("");
	}
	return;
}

inline void guass(int n) {
	for(int i = 1; i <= n; ++i) {
		int t = i + 1;
		while(t <= n && fabs(a[t][i]) <= fabs(a[i][i]))++t;
		if(t <= n) {
			for(int j = 1; j <= n + 1; ++j)swap(a[t][j], a[i][j]);
		}
		db kk = a[i][i];
		for(int j = 1; j <= n + 1; ++j)a[i][j] /= kk;
		for(int j = 1; j <= n; ++j) {
			if(j == i)continue;
			db kk = a[j][i];
			for(int k = 1; k <= n + 1; ++k) {
				a[j][k] -= a[i][k] * kk;
			}
		}
	}
	// out(n);
	return ;
}

inline void solve() {
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			// if(i != j)
			for(int k = 1; k <= m; ++k) {
				if(hsh[i][k] == hsh2[j][m - k + 1]) {
					a[i][j] += inv[m - k];
				}
			}
		}
		// a[i][i] = 1;
		a[i][n + 1] = -inv[m];
	}
	for(int i = 1; i <= n; ++i)a[n + 1][i] = 1;
	a[n + 1][n + 2] = 1;
	// out(n + 1);
	guass(n + 1);
	for(int i = 1; i <= n; ++i)printf("%.9lf\n", a[i][n + 2]);
	return ;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%s", s);
		for(int j = 0; j < m; ++j) {
			b[i][j + 1] = s[j] - '0';
		}
	}
	init();
	solve();
	return 0;
}

夏晓光(loveJY)的博客

P6125 [JSOI2009]有趣的游戏 && P3706 [SDOI2017]硬币游戏

多项式半家桶