组合意义天地灭

· · 题解

题意：

p(i)=ui+v G(x)=\prod_{i=1}^m \frac{1}{1-p(i)x}

给 n\le 10^{18}, m\le 2\times 10^5, 1\le u,v\le 10^9，求 [x^n]G(x) \bmod 998244353。

假设一个系数序列 b_{1\cdots m} 存在，满足

G(x)=\sum_{i=1}^m \frac{b_i}{1-p(i)x}

如果学过复变分析的话，可以发现这是标准的部分分式分解形式。G(x) 有简单极点（分母为线性因子互异），所以存在合法的 b，可以用留数解得。
这是 o3 告诉我的，并且它给出了更简洁的式子，但我其实看不懂这句话我通过一些学习一定程度上看懂了这句话。

反正先假设 b 存在，然后尝试去解它。
考虑解某个特殊的 i=j 的 b_j。

G(x)=\frac{b_j}{1-p(j)x}+\sum_{i=1,i\ne j}^m \frac{b_i}{1-p(i)x}

把分母乘过去。

(1-p(j)x)G(x)=b_j+\sum_{i=1,i\ne j}^m b_i\frac{1-p(j)x}{1-p(i)x}

取 x=\frac{1}{p(j)}，有 1-p(j)x=0，可以把那个 \sum 消掉。

b_j=(1-\frac{p(j)}{p(j)})G(\frac{1}{p(j)})

不能直接消成 b_j=0\times G(\frac{1}{p(j)})=0，因为 G(\frac{1}{p(j)}) 代进去算的话会有一个项是 \frac{1}{1-\frac{p(j)}{p(j)}}，所以整个 G(\frac{1}{p(j)}) 算出来是 \infin，0\times \infin 没有定义。
形式化地说就是，G(x) 在 x=\frac{1}{p(j)} 处有一个极点。

o3 说这里应该“用留数定理显式计算极限”，不过我不会高等的工具，所以我代入 G(x) 的定义式 \prod_{i=1}^m \frac{1}{1-p(i)x}。

b_j=(1-\frac{p(j)}{p(j)})\prod_{i=1}^m \frac{1}{1-\frac{p(i)}{p(j)}}

把 \prod 里面 i=j 的项摘出来消掉，这样就没有极点了，然后通分推一推。

\begin{aligned} b_j &= \prod_{i=1,i\ne j}^m \frac{1}{1-\frac{p(i)}{p(j)}}\\ &= \prod_{i=1,i\ne j}^m \frac{1}{\frac{p(j)-p(i)}{p(j)}}\\ &= \prod_{i=1,i\ne j}^m \frac{p(j)}{p(j)-p(i)}\\ &= p(j)^{m-1}\prod_{i=1,i\ne j}^m \frac{1}{p(j)-p(i)}\\ \end{aligned}

往 \prod 里面代入 p(i) 的定义式。

\begin{aligned} b_j &= p(j)^{m-1}\prod_{i=1,i\ne j}^m \frac{1}{p(j)-p(i)}\\ &= p(j)^{m-1}\prod_{i=1,i\ne j}^m \frac{1}{(uj+v)-(ui+v)}\\ &= p(j)^{m-1}\prod_{i=1,i\ne j}^m \frac{1}{u(j-i)}\\ &= \frac{p(j)^{m-1}}{u^{m-1}}\prod_{i=1,i\ne j}^m \frac{1}{j-i}\\ \end{aligned}

考虑求 \prod_{i=1,i\ne j}^m (j-i)，拆成 i<j 和 i>j 两个部分，前者的贡献是 (j-1)!，后者的贡献是 (-1)^{m-j}(m-j)!。

b_j = \frac{p(j)^{m-1}}{u^{m-1}(j-1)!(-1)^{m-j}(m-j)!}

大功告成！

然后代入到 G(x)=\sum_{i=1}^m \frac{b_i}{1-p(i)x}。
注意到根据经典式子（在原题中其实是先推出这个式子，然后再写成上面“题意”里的式子），\frac{1}{1-p(i)x}=\sum_{k=0}^{\infin}p(i)^kx^k，所以有

\begin{aligned} [x^n]G(x)&=\sum_{i=1}^m \frac{p(i)^{m-1}}{u^{m-1}(i-1)!(-1)^{m-i}(m-i)!}p(i)^n\\ &=\sum_{i=1}^m \frac{p(i)^{n+m-1}}{u^{m-1}(i-1)!(-1)^{m-i}(m-i)!} \end{aligned}

时间复杂度 \Theta(m\log n)，空间复杂度 O(1)。