SDOI2017 硬币游戏

$$ \text{设}p\left( S \right) \text{表示字符串}S\text{出现的概率} \\ \text{设}P_i\text{为第}i\text{个模式串,}p_i\text{为第}i\text{个人赢的概率} \\ \text{对于第}i\text{个人，我们可以列方程} \\ \text{设}N_i\text{为不能使第}i\text{个人赢的字符串} \\ p\left( N_iP_i \right) =\sum_{1\le j\le n}{p_j\sum_{1\le l\le m}{\frac{\left[ Suffix\left( P_j,l \right) =Prefix\left( P_i,l \right) \right]}{2^{m-l}}}} \\ \text{即考虑所有能让第}i\text{个人赢的字符串，这个串一定是由一个不能使}i\text{赢的字符串加上一些其他东西得到的}. \\ \text{因为我们要列方程组，所以如果}P_j\text{的一个长度为}l\text{的后缀与}P_i\text{的一个前缀相等,那么使得}P_j\text{能赢的字符串加上若干字符}\left( m-l\text{个} \right) \\ \text{就可以使得}i\text{赢} \\ \text{同时，出现任意长度为}i\text{的字符串的概率是}2^{-i} \\ \text{同时}p\left( N_iP_i \right) =p\left( N_i \right) p\left( P_i \right) \\ \text{又因为所有}p\left( N_i \right) \text{相等} \\ \text{所以现在有了}n+\text{1个未知数}\left( p\left( N \right) \text{和}p_1,p_2….p_3 \right) \\ \text{算上}\sum_{1\le i\le n}{p_i}=\text{1后共计}n+\text{1个方程，高斯消元即可} $$

#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <iostream>
using int_t = long long int;
using real_t = long double;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 600;
const int_t SEED = 233;
const int_t mod = 998244353;
const real_t EPS = 1e-8;
int_t prefix[LARGE + 1][LARGE + 1];
real_t pown2[LARGE + 1] = {1};
real_t mat[LARGE + 1][LARGE + 1];
int_t pow_inv[LARGE + 1] = {1};
int_t n, m;
int_t power(int_t base, int_t index) {
    const auto phi = mod - 1;
    index = (index % phi + phi) % phi;
    base = (base % mod + mod) % mod;
    int_t result = 1;
    while (index) {
        if (index & 1) result = result * base % mod;
        index >>= 1;
        base = base * base % mod;
    }
    return result;
}
int main() {
    cin >> n >> m;
    for (int_t i = 1; i <= n; i++) {
        static char buff[1 << 10];
        scanf("%s", buff + 1);
        for (int_t j = 1; j <= m; j++) {
            prefix[i][j] =
                (prefix[i][j - 1] + power(SEED, j - 1) * buff[j] % mod) % mod;
            pow_inv[j] = power(SEED, -j);
            pown2[j] = pown2[j - 1] / 2;
        }
    }
    for (int_t i = 1; i <= n; i++) {
        for (int_t j = 1; j <= n; j++) {
            for (int_t k = 1; k <= m; k++) {
                if (prefix[i][k] ==
                    (2 * mod + prefix[j][m] - prefix[j][m - k]) % mod *
                        pow_inv[m - k] % mod) {
                    mat[i][j] += pown2[m - k];
                }
            }
        }
        mat[i][n + 1] = -pown2[m];
        mat[n + 1][i] = 1;
    }
    mat[n + 1][n + 2] = 1;
    int_t len = n + 1;
    for (int_t i = 1; i <= len; i++) {
        for (int_t j = i + 1; j <= len; j++) {
            if (mat[i][i] == 0) mat[i][i] = EPS;
            real_t f = mat[j][i] / mat[i][i];
            for (int_t k = i; k <= len + 1; k++) {
                mat[j][k] -= f * mat[i][k];
            }
        }
    }
    for (int_t i = len; i >= 1; i--) {
        if (mat[i][i] == 0 && mat[i][len + 1] == 0) continue;
        mat[i][len + 1] /= mat[i][i];
        mat[i][i] = 1;
        for (int_t j = i - 1; j >= 1; j--) {
            real_t f = mat[j][i];
            mat[j][i] = 0;
            mat[j][len + 1] -= f * mat[i][len + 1];
        }
    }
    std::cout.setf(std::ios::fixed);
    cout << std::setprecision(10);
    for (int_t i = 1; i <= n; i++) {
        cout << mat[i][len + 1] << endl;
    }
    return 0;
}