多项式？[瀑布死亡舞]

里面涉及到了一个东西。

考虑你有 n 个球丢在一个箱子里面，其中一个是红球，每次抽出一个，不放回，抽到红球的期望步数。

由于不放回，相当于给 n 个球随机分配一个排列，按照这个排列抽。

则红球期望步数就是红球的期望下标，显然是

加强。

假设每个球有一个大小 w_i ，在剩余的求中抽出 i 的概率是 问这时候抽出红球的步数。

还是考虑排列。我们把红球 i 和每个球 j 分别考虑。i, j 两个球中，先抽出 j 的概率是 于是我们有： 代表抽出球 i 的期望步数。

继续加强，虽然这个影响不大。

考虑抽出每个球需要时间 t_i。问期望时间。同理有： 进一步加强。

目前求一个 f_i 的复杂度为 O(n)。考虑我们要求所有 f_i。 引入多项式科技 假设 c_v 为 w_i = v 的球的 t_i 和。 注意到这实际上是一个多项式多点求值。

我们求和多个 的和可以通过分治 NTT。

O(nlog²n)

但实际上原题有个更好的性质，∑w_i ≤ 1e5。所以 w_i 只有根号种，暴力即可。