SDOI2017 硬币游戏
标签
AC 自动机，高斯消元，状态优化这个题的字符串只有 \(2\) 种字符。
有 \(n\) 个人，每个人有一个长度为 \(m\) 的字符串 \(s_i\)（\(s_i\) 互不相同）。现在开始生成一个字符串 \(S\)：
- 每次随机一个字符加到 \(S\) 末尾。
- 如果 \(s_i\) 是 \(S\) 的子串（后缀），那么游戏结束，第 \(i\) 个人获胜。
求出每个人获胜的概率。
\(n, m \le 300\)
暴力
这种多串匹配问题很容易想到 AC 自动机，于是我们把他建出来。就有了一个极其暴力的做法：令 \(p_i\) 表示经过节点 \(i\) 的期望次数，那么第 \(i\) 个人获胜的概率就是 \(x_i = p_{ending_i}\)，\(ending_i\) 表示 \(s_i\) 在 acam 上对应的节点。转移按照 \(go_{u, 0/ 1}\) 走就行了：\(p_{go_{u, 0/ 1}} \leftarrow \frac{1}{2}p_u\)。（注意 \(ending_i\) 不能转移了）
于是我们就列出了 \(O(nm)\) 个方程，暴力高斯消元得到一个 \(O(n^3m^3)\) 的做法。
于是你就通过了这个题的 \(40pts/\)弱化版：JSOI2009 有趣的游戏
可能有利用每个方程大部分系数都是 \(0\) 模拟高斯消元的做法，但是我不会。
正解
看不懂大部分题解的神人做法，只学会了无脑做法。
因为有环，所以肯定是要高斯消元的，所以状态数就只能是 \(O(n)\) 级别。也就是说我们要剪掉一些状态。
因为我们对于每个人都要求答案，根据 ”求谁设谁“ 的原则，我们就把 \(x_1 \sim x_n\) 当成未知数。（看做 \(x_1 \sim x_n\) 都知道了。）
现在尝试用 \(x_1 \sim x_n\) 表示出所有的 \(p_u\)，观察一下转移有啥特点，对于一个点 \(u\) 来说，能转移到 \(u\) 的点 \(v\) 只有两类：
- \(u\) 的父亲 \(fa_u\)。
- 从某些深度 \(d_v \ge d_u\) 的 \(v\) 转移过来。
写出来就是：
我们可以得到： \(p_{fa} = 2p_u - \sum p_v\)。根据 \(d_v \ge d_u\) 的性质，从下到上进行递推即可。（求 \(p_{fa}\) 时 \(p_u, p_v\) 都已经求出 ）。
然后就要来找方程了，对于那些有 trie 树上有两个儿子的节点 \(u\)，\(p_u\) 有两种表示方式，而这两种方式的结构应该是一样的，就列出了 \(1\) 个方程。那一共有多少个 \(u\) 呢？答案是 \(n - 1\) 个，因为每出现一个这样的 \(u\)，trie 树就多几个分支。从 \(1\) 个变成 \(n\) 个，所以有 \(n - 1\) 个这样的 \(u\)。
还有一个怎么办？\(\sum x_i = 1\) 来凑。
\(n\) 个未知数，\(n\) 个方程，就可以高斯消元了。
复杂度
时间复杂度：\(O(n^3 + nm)\)。瓶颈是高斯消元。
空间复杂度：如果对于每个节点都记下 \(x_i\) 的系数，那么空间就达到了 \(O(n^2m)\)，应该会被卡掉。但是可以对于每个 \(x_i\) 单独做，就是 \(O(n^2 + nm)\) 的了。
精度问题
因为高斯消元多次使用除法，很容易爆掉，比如我 \(60pts\)。
注意找到某一行的 \(a_{x, i} \ne 0\) 时，不能选一个 \(abs() > eps\) 的，要选 \(abs()\) 最大的那个。
总结
在暴力的基础上，减少状态来优化复杂度，不难找到这 \(n\) 个状态，如何表示出其他 \(p_u\) 以及如何找到方程还是很有难度的。（毕竟是个黑题。）