题解：P10325 超越（Transcendent）

· · 题解

设 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 的时间常数更优。