CF780F Axel and Marston in Bitland 笔记

观察行动字符串的特性：

• 前缀相同。
• 长度为 $2^k$。
• 同一长度下，只有正（P 开）和反（B 开）两种字符串，并且长度为 $2L$ 的 P 字符串由 $L$ P $+$ $L$ B 组成，$2L$ B 反之。

以上特性指向倍增。

设 $f_{k,0/1,i,j}$ 表示用 P 开 / B 开长度为 $2^k$ 的字符串，能否从 $i$ 点走到 $j$ 点，使用 Floyd 思想可以做到 $O(n^3\log V)$。

注意到 Floyd，即 $f\in [0,1]$，所以 Bitset 优化可以做到 $O(\frac{n^3\log V}{\omega })$

按 $2^k$ 从大到小拼路径的时候同样使用 Bitset 存当前可以到达哪些点，每次枚举是否有新点可以到达，注意每走完一个 $2^k$，下一步需要切换是 P 开还是 B 开。这一部分时间复杂度 $O(\frac{n^2\log V}{\omega })$。