硬币游戏

硬币游戏

\(\text{AC}\)自动机建出来暴力高消复杂度是\(O((nm)^3)\)的,有\(40\)分.实际上\(\text{AC}\)自动机上记录了很多我们并不需要的状态和转移,所以复杂度降不下来.

考虑增加一个辅助变量\(x_0\)表示经过一个任意长度但没有包含任意一个给定序列的末尾节点的期望.\(x_i\)表示经过第\(i\)个同学的串的末尾节点的期望(数值上等于它获胜的概率,因为经过后游戏就结束了).

引理一:

结尾包含一个长度为\(L\)的指定串但没有包含任意一个给定序列的概率为\(\frac{1}{2^L}\).

证明一:

不会啊....

首先我们有一个非常\(naive\)的想法,如果我们想要一个串出现那我们直接在一个没有包含任意指定序列的后面加上我们想要的串不就好了吗?太有道理了吧

但是很显然你可能在加上这个串之后,它已经经过了另外一个串的结尾字符.(这个是导致每个同学的期望不同的本质原因,否则每个人的期望应该是都是\(\frac{1}{2^m}x_0\))

这样那我们用\(\frac{1}{2^m}x_0\)减去冲突(指加上这个串之后已经包含另外一个串的情况)的期望不就是我们要求的真正期望吗?

考虑冲突在什么情况下会发生:

设我们当前考虑\(i\)串,会和\(j\)串发生冲突.会发生冲突当且仅当:如果一个没有包含任意指定序列包含了\(j\)串的一个前缀,而恰好\(j\)串除去被包含的前缀后的串又是\(i\)串的前缀.

说人话就是\(j\)串的后缀和\(i\)串的前缀匹配,而没有包含任意指定序列的后缀又和\(j\)串的前缀部分相同.则对于每个\(i\)有如下方程: \[ x_i+\sum_{j=1}^nx_j\left(\sum_{k=1}^{m-[i=j]}\left[\text{prefix(i,k)=suffix(j,k)}\right]\frac{1}{2^{m-k}}\right)=\frac{1}{2^m}x_0 \] PS:\(\text{prefix(i,j)}\)表示\(i\)串的长为\(j\)的前缀,\(\text{suffix(i,j)}\)同理.\(\frac{1}{2^{m-k}}\)表示序列结尾和\(\text{prefix(j,m-k)}\)相同的概率(使用引理一).

当然还有一个方程: \[ \sum_{i=1}^nx_i=1 \] 然后直接高斯消元即可.

复杂度\(O((n+1)^3)\)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/*
* 4818.cpp
* This file is part of 4818
*
* Copyright (C) 2019 - ViXbob
*
* 4818 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 4818 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 4818. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 3e2 + 5;
const int P = 998244353;
const ull seed = 255;

int n, m;
char s[maxn][maxn];
long double mi[maxn], a[maxn][maxn], ans[maxn];
ull Hash[maxn][maxn], seedi[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

inline bool Gauss(long double a[maxn][maxn], int n) {
rep(i, 1, n) {
int p = i;
rep(j, i + 1, n) if(fabs(a[j][i]) > fabs(a[p][i])) p = j;
if(p != i) swap(a[p], a[i]);
rep(j, i + 1, n) {
long double ratio = a[j][i] / a[i][i];
rep(k, i, n + 1) a[j][k] -= ratio * a[i][k];
}
}
dep(i, n, 1) {
ans[i] = a[i][n + 1] / a[i][i];
dep(j, i - 1, 1) a[j][n + 1] -= a[j][i] * ans[i];
} return true;
}

int main() {
// freopen("1.in", "r", stdin);
n = read(); m = read(); mi[0] = 1; seedi[0] = 1;
rep(i, 1, m) mi[i] = mi[i - 1] * 0.5;
rep(i, 1, m) seedi[i] = seedi[i - 1] * seed;
rep(i, 1, n) {
scanf("%s", s[i] + 1);
rep(j, 1, m) Hash[i][j] = Hash[i][j - 1] * seed + s[i][j];
}
rep(i, 1, n) a[i][n + 1] = -mi[m], a[i][i]++;
rep(i, 1, n) a[n + 1][i] = 1; a[n + 1][n + 2] = 1;
rep(i, 1, n) rep(j, 1, n)
rep(k, 1, m - (i == j)) if(Hash[i][k] == Hash[j][m] - Hash[j][m - k] * seedi[k])
a[i][j] += mi[m - k];
// rep(i, 1, n + 1) {
// rep(j, 1, n + 2) cerr << a[i][j] << " ";
// cerr << endl;
// }
Gauss(a, n + 1);
rep(i, 1, n) printf("%.10lf\n", (double)(ans[i]));
return 0;
}