P6125 [JSOI2009] 有趣的游戏

· · 题解

发现这题其实并没有自己想象中的那么难呢。

Solution

首先可以发现这个题和字符串匹配有关，那么先把所有模式串扔到 ACAM 上，把每个串的结尾的点标记为对应人的获胜点。

然后考虑在自动机上 dp 求概率。设 f_{u} 表示某个人在自动机上的 u 点的时候的获胜概率，那么转移有三种情况：

显然答案为 f_0，表示从空串开始的概率。

然后我们发现在自动机上会出现环，也就是说这些转移方程是互相依赖的，那么我们就不能直接转移，否则会出现后效性。此时这些方程形成了一个方程组，所以我们直接将所有 f 看作未知数，构造系数矩阵，然后高斯消元解出每个值即可。

对每个人跑一边上面的流程，求出答案输出。时间复杂度 O(n^4l^3)。

:::success[Code]

int n, l, m;
long double P[N];
char s[N];
int trie[N][26], idx;
int ed[N], fail[N];
long double a[5005][5005];

inline void insert (char *s, int id) {
    int p = 0, len = strlen(s);
    for (int i = 0; i < len; ++ i) {
        int c = s[i] - 'A';
        if (!trie[p][c]) trie[p][c] = ++ idx;
        p = trie[p][c];
    }
    ed[p] = id;//记录获胜点
}

inline void Success() {
    queue<int> q;
    for (int i = 0; i < m; ++ i) {
        if (trie[0][i]) q.emplace(trie[0][i]);
    }
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        if (!ed[p]) ed[p] = ed[fail[p]];//如果是某个人字符串的后缀，那么走到这个点的时候实际上这个人就已经赢了，所以传递标记
        for (int c = 0; c < m; ++ c) {
            if (trie[p][c]) {
                q.emplace(trie[p][c]);
                fail[trie[p][c]] = trie[fail[p]][c];
            } else trie[p][c] = trie[fail[p]][c];
        }
    }
}//建立 AC 自动机

inline void Guass(int n) {
    int r = 0;
    for (int c = 0; c < n; ++ c) {
        int t = c;
        for (int i = r; i < n; ++ i) {
            if (fabsl(a[i][c]) >  fabsl(a[t][c]) + eps) t = i;
        }
        if (fabsl(a[t][c]) < eps) continue;
        for (int i = c; i <= n; ++ i) swap (a[r][i], a[t][i]);
        for (int i = n; i >= c; -- i) a[r][i] /= a[r][c];
        for (int i = r + 1; i < n; ++ i) {
            if (fabsl(a[i][c]) > eps) {
                for (int j = n; j >= c; -- j) a[i][j] -= a[i][c] * a[r][j];
            }
        }
        ++ r;
    }
    for (int i = n - 1; i >= 0; -- i) {
        if (fabsl(a[i][i]) < eps) {
            a[i][n] = 0;
            continue;
        }
        for (int j = i + 1; j < n; ++ j) {
            a[i][n] -= a[i][j] * a[j][n];
        }
    }
}//高斯消元

int main () {
    scanf ("%d%d%d", &n, &l, &m);
    for (int i = 0; i < m; ++ i) {
        long double x, y;
        scanf ("%Lf%Lf", &x, &y);
        P[i] = 1.0 * x / y;
    }
    for (int i = 1; i <= n; ++ i) {
        scanf ("%s", s);
        insert (s, i);
    }
    Success();
    for (int i = 1; i <= n; ++ i) {
        for (int p = 0; p <= idx + 1; ++ p) for (int q = 0; q <= idx + 1; ++ q) a[p][q] = 0;
        for (int p = 0; p <= idx; ++ p) {
            a[p][p] = 1;
            if (ed[p] == i) a[p][idx + 1] = 1;
            else if (ed[p] && ed[p] != i) a[p][idx + 1] = 0;
            else {
                for (int c = 0; c < m; ++ c) {
                    int q = trie[p][c];
                    if (ed[q] == i) a[p][idx + 1] += P[c];
                    else if(!ed[q]) a[p][q] -= P[c];
                }
            }
        }
        Guass(idx + 1);
        printf ("%.2Lf\n", a[0][idx + 1]);
    }
    return 0;
}

:::