CF482C Game with Strings

比较具有启发意义的题目。

首先看到 \(m \le 20\)，我们第一个想到的就是状压 DP，设 \(f_i\) 为选取位置集合为 \(i\) 时期望多少步确定，显然转移是简单的，比较困难的地方在当 \(i\) 唯一确定一个串（这个串需要你枚举出来）时，\(f_i = 0\)，而这一步需要 \(O(nm2^m)\) 的复杂度。

一个比较容易想到的优化是，我们不去枚举串，而是在转移的过程中取总的算一下，发现将原本的系数 \(1\) 变为 \(g_i\) 表示 \(i\) 状态下有几个没有被确定的串，这在原本的 DP 中都会造成 \(1\) 的贡献。而 \(g_i\) 用高维前缀和是好求的，于是我们在 \(O(m2^m)\) 内做完了本题。