BZOJ1444 [JSOI2009]有趣的游戏
Solution
联想到神奇的 Penney’s game:
一个公平的硬币,被两个无聊的小孩连续抛掷,直到最近三次硬币抛掷结果是“正反反”或者“反反正”。如果是前者,第一个小孩胜利,后者第二个小孩胜利。问谁的胜率更大。答案是前者胜率是后者的三倍!
这道题是一道神奇的在 AC 自动机上的概率 DP。假设到达第 i 个非根结点的概率为 $P_i$,则 $P_i$ 的值为所有能转移到节点 i 的节点选到的概率 * 选到 i 表示的字母的概率。特别地,一个节点不能由某个人的胜利状态转移到(因为转移到上面的时候游戏已经结束)。上面列出的方程组与所有人胜利概率之和为 1 这一条件连立,高斯消元解出这一方程组即可。
注意构造矩阵的时候绝对不能偷懒 T^T 在这里 WA 好久…… 为什么这里写的错到离谱,运行时间还和 AC 时间一样 T^T
还有高斯消元得到的答案可能会出现 -0.0,输出的时候要特判。C++ 里面的 -0 机制真是神奇~
Code
#include <bits/stdc++.h> using namespace std; #define N 12 #define S 105 #define strn *str - 'A' int n, l, m, s, d[N]; char str[N]; long double p[N], mat[S][S]; struct trie_node { int id; trie_node *son[10], *fail, *last; bool flag; trie_node() {} trie_node(int _id) : id(_id), son(), fail(), last(), flag() {} void *operator new(size_t); }nodes[S]; void *trie_node::operator new(size_t) { return nodes[s] = trie_node(s), &nodes[s++]; } struct Aho_Corasick_automaton { typedef trie_node node; node *root; Aho_Corasick_automaton() { root = new node(); } void insert(char *str) { node *p = root; while (*str) { if (p->son[strn] == NULL) p->son[strn] = new node(); p = p->son[strn]; ++str; } p->flag = true; } void build_AC_Automaton() { queue<node*> q; root->fail = root; for (int i = 0; i < m; ++i) if (root->son[i] == NULL) root->son[i] = root; else q.push(root->son[i]), root->son[i]->fail = root; while (!q.empty()) { node *t = q.front(); q.pop(); for (int i = 0; i < m; ++i) { if (t->son[i] == NULL) t->son[i] = t->fail->son[i]; else q.push(t->son[i]), t->son[i]->fail = t->fail->son[i]; } } } void build_matrix(long double mat[S][S]) { for (int i = 0; i < s; ++i) { if (i) mat[i][i] = -1; if (!nodes[i].flag) for (int j = 0; j < m; ++j) mat[nodes[i].son[j]->id][i] += p[j]; } for (int i = 0; i < s; ++i) mat[0][i] = nodes[i].flag; mat[0][s] = 1; } }; Aho_Corasick_automaton ac; void gauss(int n, long double mat[S][S]) { for (int i = 0; i < n; ++i) { int t = i; for (int j = i + 1; j < n; ++j) if (fabs(mat[j][i]) > fabs(mat[t][i])) t = j; if (t != i) for (int j = 0; j <= n; ++j) swap(mat[i][j], mat[t][j]); for (int j = i + 1; j < n; ++j) { double t = mat[j][i] / mat[i][i]; for (int k = 0; k <= n; ++k) mat[j][k] -= mat[i][k] * t; } } for (int i = n - 1; i >= 0; --i) { mat[i][n] /= mat[i][i]; mat[i][i] = 1; for (int j = i - 1; j >= 0; --j) mat[j][n] -= mat[j][i] * mat[i][n], mat[j][i] = 0; } } int main() { cin >> n >> l >> m; for (int x, y, i = 0; i < m; ++i) { cin >> x >> y, p[i] = y ? 1.0 * x / y : 0; if (y == 0) while (1) {} } for (int i = 1; i <= n; ++i) { scanf("%s", str); ac.insert(str); d[i] = s - 1; } ac.build_AC_Automaton(); ac.build_matrix(mat); gauss(s, mat); cout << fixed << setprecision(2); for (int i = 1; i <= n; ++i) { if(mat[d[i]][s] > 0) cout << mat[d[i]][s] << endl; else cout << 0.00 << endl; } }