周末同学们非常无聊，有人提议，咱们扔硬币玩吧，谁扔的硬币正面次数多谁胜利。

大家纷纷觉得这个游戏非常符合同学们的特色，但只是扔硬币实在是太单调了。

同学们觉得要加强趣味性，所以要找一个同学扔很多很多次硬币，其他同学记录下正反面情况。

用表示正面朝上，用表示反面朝上，扔很多次硬币后，会得到一个硬币序列。比如表示第一次正面朝上，后两次反面朝上。

但扔到什么时候停止呢？大家提议，选出 $n$ 个同学，每个同学猜一个长度为 $m$ 的序列，当某一个同学猜的序列在硬币序列中出现时，就不再扔硬币了，并且这个同学胜利。为了保证只有一个同学胜利，同学们猜的 $n$ 个序列两两不同。

很快， $n$ 个同学猜好序列，然后进入了紧张而又刺激的扔硬币环节。你想知道，如果硬币正反面朝上的概率相同，每个同学胜利的概率是多少。

题解

哎呀好气呀，又到了团长看着就恶心的概率题辣。。

mmp，我在场上的时候真的是连样例都没有看懂啊。但是概率的题能看懂样例就有鬼啦。。

当时感觉可能是AC自动机上dp什么的。。但是最后这个部分分也没有想出来。。

好吧团长要正儿八经地写题解了。。

设 $P(S)$ 为到达一个可能的硬币序列 $S$ 的概率，特别的，若某位同学为 $A$ ，或者你乐意叫他张三李四王五都可以，那么 $P(A)$ 为同学 $A$ 胜利的概率。

设一个状态 $N$ 为一个硬币序列，这个硬币序列中的任意子串不会使得任意玩家胜利，那么现在若在 $N$ 后面接上玩家 $A$ 的硬币序列，玩家 $A$ 就可能胜利。

为什么是可能胜利呢？考虑一个玩家 $A$ 的硬币序列为 TTH，玩家 $B$ 的硬币序列为 HTT 这样如果状态 $N$ 的末尾为 H 那么在后面加上 TT 后玩家 $B$ 胜利，在这种情况下再加上 H 得到 $N$ 后面接 $A$ 硬币序列的情况，若 $N$ 末尾为 HT 那么加上 T 后玩家 $B$ 胜利，再接上 TH 后得到要求的合法情况。

这种情况只会出现在玩家 $A$ 的硬币序列的某个前缀是玩家 $B$ 硬币序列的某个后缀的情况。

假设只有这两个玩家，那么一个方程是显然的：

P(N + A) = P(A) + 0.75P(B)

尝试把这种情况拓展一下，对于两个任意的玩家 $A, B$ ，计算出所有 $A$ 的硬币序列的前缀是 $B$ 的硬币序列的后缀的长度 $k$ ，那么由 $P(B)$ 达到到 $P(N + A)$ 的概率应该是：

\sum\limits_{k} \frac {1} {2 ^ {m - k}}

这个式子可以用 KMP 处理出来。

对于第 $i$ 个玩家和第 $j$ 个玩家，我们记上面的式子为 $Q_{i, j}$

设 $P(N)$ 为 $x_0$ ，某个玩家 $i$ 胜利的概率为 $x_i$ ，那么这样可以列出 $n$ 个方程，第 $i$ 个方程的形式如下：

x_i + \sum\limits_{j = 1}^{n} Q_{i, j} = \frac {1} {2 ^ m}x_0

但是这样有一个问题，现在已经列出 $n$ 个方程，但是加上变量 $x_0$ 一共有 $n + 1$ 变量，所以我们需要第 $n + 1$ 个方程。

由于所有玩家胜利的概率之和是 $1$ ，所以第 $n + 1$ 个方程是显然的：

\sum\limits_{i = 1}^{n} x_i = 1

代码

咸鱼团长第 $n$ 次学习高斯消元。。

#include <cstdio>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <cfloat>
#include <algorithm>
const int MAX_N = 300 + 5;
const int MAX_M = 300 + 5;
const long double EPS = 1e-10;
int n, m, fail[MAX_N][MAX_M];
long double pows[MAX_M], a[MAX_N][MAX_M];
char s[MAX_N][MAX_N];
inline long double check(int x, int y) {
    long double res = 0;
    int max = 0;
    for (int i = 1; i <= m; i++) {
        while (max && s[x][max + 1] != s[y][i]) max = fail[x][max];
        if (s[x][max + 1] == s[y][i]) max++;
    }
    while (max) res += pows[m - max], max = fail[x][max];
    return res;
}
inline void gaussJordan(int n) {
    for (int i = 1; i < n; i++) {
        int id = i;
        for (int j = i + 1; j < n; j++) if (fabs(a[j][i]) > fabs(a[id][i])) id = j;
        if (id != i) for (int j = i; j <= n; j++) std::swap(a[i][j], a[id][j]);
        for (int j = 1; j < n; j++) {
            if (i != j) {
                for (int k = n; k >= i; k--) {
                    a[j][k] -= a[i][k] / a[i][i] * a[j][i];
                }
            }
        }
    }
    for (int i = 1; i < n; ++i) a[i][n] /= a[i][i], a[i][i] = 1;
}
inline void prepare() {
    // KMP prepare
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++) {
            int k = fail[i][j];
            while (k && s[i][k + 1] != s[i][j + 1]) k = fail[i][k];
            fail[i][j + 1] = s[i][k + 1] == s[i][j + 1] ? k + 1 : 0;
        }
    }
    pows[1] = 0.5;
    for (int i = 2; i <= m; i++) pows[i] = pows[i - 1] * 0.5;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = check(i, j) + (i == j ? 1.00 : 0.00);
        }
    }
    for (int i = 1; i <= n; i++) a[n + 1][i] = 1, a[i][n + 1] = -1;
    a[n + 1][n + 2] = 1;
#ifdef DBG
    for (int i = 1; i <= n + 1; i++) {
        for (int j = 1; j <= n + 2; j++) {
            printf("%.10Lf ", a[i][j]);
        }
        puts("");
    }
#endif
}
int main() {
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s[i] + 1);
    }
    prepare();
    gaussJordan(n + 2);
    for (int i = 1; i <= n; i++) {
        printf("%.10lf\n", (double)a[i][n + 2]);
    }
    return 0;
}

「SDOI2017」硬币游戏 - KMP，高斯消元

Contents

题解

代码