自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:56:56，当前版本为作者最后更新于2024-04-05 22:48:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

设 $p_j=a_j/b_j$，下面再出现的 $a,b$ 就不再是这个意思了（因为记号不太够用）。根据简单的生成函数知识可得（单阶段恰好 $k$ 次成功的概率，就是连续失败 $k-1$ 次的概率乘以单次成功概率）

$$\sum_{k\geq 0}f_kx^k=\prod_{j=1}^m\left( \sum_{k=1}^\infty p_j(1-p_j)^{k-1}x^k\right)=\prod_{j=1}^m \frac{p_jx}{1-(1-p_j)x} $$

所以答案就是 $x_i=\cos (i \pi/n)$：

$$\frac{1}{2n}\sum_{i=1}^{2n} \left( \prod_{j=1}^m \frac{p_j x_i}{1-(1-p_j)x_i}\right) $$

这个形式还是不太方便，设 $q_j=1-p_j$，$M$ 是不同的 $p_1,\cdots,p_m$ 的个数，我们做分式分解。时间开销 $\mathcal O(m \log^2 m)$ 稍有点大，不过这是值得的：

$$\prod_{j=1}^m \frac{p_jx}{1-(1-p_j)x}=C+\sum_{j=1}^M\frac{P_j(x)}{(1- q_j' x)^{k_j}} $$

现在我们就只用对分解后的 $M$ 项分开考虑了，注意多出来的单项 $C$ 是因为原式不是真分式（分子不小于分母度数）。现在原问题就拆解为了一些简单的子问题，我们有两种算法可以处理它。

---

算法 1

利用单位根的性质，将 $x_i$ 表示为 $(\omega_{2n}^i+\omega_{2n}^{-i})/2$，设

$$G(x)= \frac{P(x)}{(1-qx)^k} \circ \left( \frac{x+x^{-1}}{2}\right) $$

那么就只需要对 $i$ 求出 $G(\omega_{2n}^i)$ 之和即可。继续对 $G(x)$ 做分式分解，在 $4q^2\not \equiv 1 \pmod{998244353}$ 时可以写为

$$G(x)=\frac{A(x)}{(1-\alpha x)^k}+\frac{B(x)}{(1-\alpha x)^k} $$

而对于 $4q^2\equiv 1\pmod{998244353}$ 的时候 $\alpha = \beta$，要合并为 $2k$ 重根计算。考虑对一定范围内的 $k$ 分别求出

$$\sum_{i=1}^{2n} \frac{1}{(1- \alpha \omega_{2n}^i)^k} $$

可以考虑先求出多项式 $D(t)$：

$$\begin{aligned}D(t)&=\prod_{i=1}^{2n}\left( 1-\frac{t}{1-\alpha \omega_{2n}^i}\right) \\ D(t) &= \prod_{i=1}^{2n}\left( \frac{(1-t)-\alpha\omega_{2n}^i}{1-\alpha \omega_{2n}^i}\right) \\ (1-\alpha^{2n})D(t)&=\prod_{i=1}^{2n}((1-t)-\alpha \omega_{2n}^i) \\ (\alpha^{-2n}-1)D(t) &= \left(\frac{1-t}{\alpha} \right)^{2n}-1 \end{aligned} $$

这个有什么用呢？我们求出了 $y_i=1/(1-\alpha \omega_{2n}^i)$ 所满足的代数方程，就可以根据

$$D(t)=\prod_{i=1}^{2n}(1-y_i t)$$ $$\begin{aligned}\sum_{i=1}^{2n}\frac{y_i}{1-ty_i}&=-(\ln D(t))' \\ \sum_{j=0}^\infty t^j\sum_{i=1}^{2n}y_i^{j+1}&=-\frac{D'(t)}{D(t)}\end{aligned} $$

用一次多项式 $\ln$ 直接计算出各 $y_i^k$ 之和。此算法需要高度优化模板常数，否则可能无法通过。

---

算法 2

和算法 1 的整体思路相同，但是在一些操作上进行了常数优化。

回到原式中，考虑将和式中的每一部分都写为

$$\frac{P(x)}{(1-qx)^k}=\sum_{j=0}^{k-1} \frac{a_j}{(1-qx)^{j+1}} $$

（实际上，在进行分式分解的时候，不进行最后一步的多项式平移，就能对应得到系数 $a_0,\cdots,a_{k-1}$）

我们尝试直接分析 $x_i$ 所满足的代数方程是什么样的：

$$F(x)=\prod_{k=0}^{2n-1}\left( x-\cos \frac{k\pi}{n}\right) $$

通过打表等方法可以发现 $F(x)=2^{2-2n}(x^2-1)U_{n-1}(x)^2$，其中 $U_n(x)$ 表示 $n$ 次第二类 Chebyshev 多项式，具体的证明可以参见附页。

用算法 1 的方法，设

$$D(t)=\prod_{i=1}^{2n} \left( 1-\frac{t}{1-qx_i}\right) $$

就直接得到

$$F(q^{-1}) D(t) = F\left( \frac{1-t}{q}\right)$$

现在问题是如何求出 $\hat F=F((1-t)/q)$ 的前 $k$ 项系数。由于 $F(t)$ 显然是微分有限的：

$$4n^2F-tF'+(1-t^2)F''+4n^22^{1-2n}=0$$

所以 $\hat F$ 也必然微分有限，可以整式递推求出系数。经过一些计算可得其 ODE 为

$$4n^2\hat F+(1-t)\hat F'-((1-t)^2-q^2)\hat F''+4n^22^{1-2n}=0 $$

直接提取系数计算即可。然后就还是和之前一样，计算 $\ln D(t)$ 的系数就得到了 $1/(1-qx_i)^k$ 之和。需要注意的是求 $\hat F$ 的系数时，前两项需要单独求解，而 Chebyshev 多项式的点值 $U_n(q)$ 可以用矩阵快速幂等方法在 $\Theta(\log n)$ 的时间复杂度计算。

此做法也是 std 使用的方法。

---

相比于算法 1，算法 2 对于每组 $q$ 计算时不需要做复合 $x+x^{-1}$，也不需要做多余的分式分解，且后续也可以不需要扩域算卷积这种麻烦的事。只不过代数推导方面会麻烦一些。

两种算法的时间复杂度都为 $\mathcal O(m \log^2 m+m \log n)$，但算法 2 的时间常数更优。