[洛谷P3175][HAOI2015]按位或

某金牌爷给我们讲了讲多项式相关的题目,这是第一道。
本题我们发现一般的期望DP难以优化,但是我们可以基于下面这个式子进行计算:
$$ans=\sum_{i=0}^{\infty} $(第i轮未结束的概率)
令$cnt(x)$表示x的二进制中1的个数。
我们可以来容斥一波。枚举每一个未结束的状态,然后让其他位置随便取,再计算对答案的贡献,可以得到下面这个式子:
$$ans=\sum_{k=0}^{\infty}\sum_{i=0}^{2^n-2} (\sum_{j\subseteq i}p_j)^k(-1)^{n-cnt(i)+1}$$
$$=\sum_{i=0}^{2^n-2}(-1)^{n-cnt(i)+1}\sum_{k=0}^{\infty}(\sum_{j\subseteq i}p_j)^k$$
$$=\sum_{i=0}^{2^n-2}(-1)^{n-cnt(i)+1}\frac{1}{1-\sum_{j\subseteq i}p_j}$$
我们只需要用FWT计算出对于所有的:
$$f(i)=\sum_{j\subseteq i}$$
那么就可以直接计算答案了。
代码巨短:

Tagged with:

发表评论