qoj14457. 缺陷解码器
有一初始为空的字符串 \(S\) 和大小为 \(m\) 的字符集 \(C\)，一直执行以下操作：
-
从 \(C\) 中随意一个字符，接在 \(S\) 后面。
-
分别令 \(S_1,S_2\) 表示 \(S\) 的 前/后 \(\lfloor\frac {|S|}2\rfloor\) 个字符构成的字串。假如 \(S\) 是一个回文串或者 \(S_1=S_2\)，那么将 \(S\) 重置为空串。
-
如果 \(S\) 未被重置，且 \(|S|=n\)，那么退出。
现在给出 \(n,m\)，问期望需要多少次操作退出？
令 \(g(s)\) 表示串 \(s\) 是否合法，合法则为 \(1\)，不合法则为 \(0\)。用 \(\varnothing\) 表示空串。
设 \(f(s)\)，表示当前状态为 \(s\) 时的答案。
- 如果 \(s\) 满足重置条件，那么 \(f(s)=f(\varnothing)\)。
- 否则，如果 \(|s|=n\)，那么 \(f(s)=0\)。
- 否则，
但是由于这个转移式有环，无法直接转移。
暴力的方法是直接高斯消元，复杂度 \(\mathcal O(m^{3n})\)。
但是这样很亏啊！
因为我们发现并不是到处都有环，假如拆掉所有指向 \(\varnothing\) 的边，剩下的转移显然无环。
由于转移是线性的，想象我们将所有从 \(\varnothing\) 出发最后回到 \(\varnothing\) 的环缩成一个 \(\varnothing\) 上的自环，那么最后剩下的唯一的转移就是 \(f(\varnothing)=\lambda f(\varnothing)+k\) 的形式，此时可以直接解出 \(f(\varnothing)\) 的值。
具体地，我们设 \(x=f(\varnothing)\)，对于所有满足重置条件的 \(s\)，我们令 \(f(s)=x\)。
那么每个点上的 \(f\) 值可以被表示成 \(kx+b\) 的形式，最后转移到 \(\varnothing\) 时就可以解出 \(x\) 的值了。
时间复杂度 \(\mathcal O(m^n)\)。
但是 \(m\) 太大了！怎么办？
由于字符之间是等价的，我们可以从左往右将第一次遇到的字符替换为 \(1,2,3,\cdots\)，答案显然不变。
状态数减少到 \(\displaystyle\sum_{i=1}^n\text{Bell}(i)\)，对于 \(n=12\) 这个值大约是 \(8\times 10^5\)。
（但是官方题解说它 \(\approx 5\times 10^6\)，不知道为啥
code