自动搬运

查看原文

来自洛谷，原作者为

	WrongAnswer_90 别爆零了

搬运于2025-08-24 23:11:21，当前版本为作者最后更新于2025-03-27 16:36:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先对 $p$ 从大到小排序，一定取一段前缀做。暴力 DP $f_{i,j}$ 表示前 $i$ 个做对了 $j$ 个。可以证明有值的项不会特别多（？？？），大概是 $\mathcal O(\sqrt{n\log{\epsilon^{-1}}})$ 级别的，所以暴力就过了。

模拟赛场上写了一个非常不牛的分块 FFT，但是 luogu 上似乎被卡精度了。首先每个位置可以看成一个 $(p_i+(1-p_i)x)$ 的多项式。序列分块，处理出 $F_i$ 表示前 $i$ 个块多项式的乘积，块内用上面的暴力 DP。两部分拼起来的时候前缀和优化一下即可做到 $\mathcal O(n\sqrt{n\log n})$。

还有一个很牛的分治。设 solve(l,r,F) 表示要处理区间 $[l,r]$，然后 $[1,l-1]$ 的所有多项式乘起来是 $F$。

对于 $[x^i]F$，如果 $i-(r-l+1)>k$，那这个 $f_i$ 在区间里一定有贡献，直接加到区间里面就行了。如果 $i+(r-l+1)<k$，那这个 $f_i$ 在区间里一定没有贡献，所以需要考虑的项只有 $[k-(r-l+1),k+(r-l+1)]$ 里面的，所以 solve 需要保留的多项式长度就是 $\mathcal O(r-l+1)$ 级别的。这样 FFT 一下就可以做到 $\mathcal O(n\log^2 n)$ 求出每一项的答案了。