P9379 Sol || 人类智慧 3.0

· · 题解

啊我怎么忘记期望次数可以拆每步概率之和了。但是也能做，提供一个容斥草过去神秘做法。

先考虑怎么计算位集合 S 变得全部已知的期望次数，设为 f(S)。设 f'(S) 为 S 中第一次有位被确定的期望次数，有 f'(S)=\sum\limits_{k=0}^{\infty}\left(\prod\limits_{i\in S}(1-p_i)\right)^k=\dfrac{1}{1-\prod\limits_{i\in S}(1-p_i)}，容易求得。由 minmax 容斥有 f(S)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}f'(T)，高维前缀和一下即可。

然后来算每个给定串的答案。尝试求出，如果隐藏的是这个给定串，那么目前已知的位集合为哪些时可以直接确定是这个串。称它们为这个给定串的好子集。

相当于可以把所有给定串的一些位换成 ?，然后问每个给定串，它有多少种换的方案满足在所有给定串的方案中只出现了一次。显然好子集的数量之和至多是 O(3^l) 的，并且一个好子集的超集必定都是好子集，所以搜一遍均摊就是对的。

现在已知了某个给定串的好子集集合 A，我们想知道取到任何一个好子集的期望步数（“取到”指当前已知的位集合包含这个好子集）。考虑再来一个 minmax 容斥，设 g_S 表示 A 的子集 S 中的集合都被取到（也就是它们的并被取到）的期望步数。那么答案为 \sum\limits_{B\subseteq A}(-1)^{|B|+1}f(\bigcup\limits_{T\in B}T)。

考虑每个 f(S) 的贡献系数 h_S=\sum\limits_{B\subseteq A}\left[\left(\bigcup\limits_{T\in B}T\right)=S\right](-1)^{|B|+1}。\left(\bigcup\limits_{T\in B}T\right)=S 不好处理，再容斥设 h'_S=\sum\limits_{B\subseteq A}\left[\left(\bigcup\limits_{T\in B}T\right)\subseteq S\right](-1)^{|B|+1}=\sum\limits_{i=0}^k\binom{k}{i}(-1)^{k+1}=-[k=0]。其中 k 是 \subseteq S 的好子集数量。所以 h'_S=[S\notin A]\cdot (-1)。而 h_S 是 h'_S 的高维差分。答案即 \sum\limits_{S} h_S f(S)。

有一个很诡异的操作：我们将 h'_S 整体加上 1。

根据差分定义，这样只会导致 h_0 变化，而 f(0)=0 所以答案不变，无所谓。而这时变为了 h_S=[S\in A]。那么显然做高维差分以及计算答案时只遍历好子集项，就是正确的。加起来 O(3^l l)。

:::info[fun fact：我是怎么想到这个操作的] 我没想到。

我只是推式子的时候脑抽推成了 \sum\limits_{i=0}^k\binom{k}{i}(-1)^{k+1}=\color{red}[k>0]。

然后就按着这个东西写了 O(n2^l l)，然后样例对了，然后自然地只遍历好子集项做到了 O(3^l l)，然后过了，然后写题解，诶？我推了个什么东西？？ :::

其实就算不做这个整体加，这个高维差分初值的形式仍然极为特殊，应该也是能处理的。

qoj 过了。洛谷没卡过去，摆了。

总感觉这个做法有一些没被发掘的高妙性质，求大佬指点。