题解：P11918 [PA 2025] 考试 / Egzamin

WrongAnswer_90 · 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) 求出每一项的答案了。