专栏文章

组合意义天地灭

ffangzichang
题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mip5ibys
此快照首次捕获于
2025/12/03 06:29
3 个月前
此快照最后确认于
2025/12/03 06:29
3 个月前
查看原文
题意：
p(i)=ui+vp(i)=ui+v G(x)=∏i=1m11−p(i)xG(x)=\prod_{i=1}^m \frac{1}{1-p(i)x}
给 n≤1018,m≤2×105,1≤u,v≤109n\le 10^{18}, m\le 2\times 10^5, 1\le u,v\le 10^9，求 [xn]G(x) mod 998244353[x^n]G(x) \bmod 998244353。
假设一个系数序列 b1⋯mb_{1\cdots m} 存在，满足
G(x)=∑i=1mbi1−p(i)xG(x)=\sum_{i=1}^m \frac{b_i}{1-p(i)x}
如果学过复变分析的话，可以发现这是标准的部分分式分解形式。G(x)G(x) 有简单极点（分母为线性因子互异），所以存在合法的 bb，可以用留数解得。
这是 o3 告诉我的，并且它给出了更简洁的式子，但我其实看不懂这句话我通过一些学习一定程度上看懂了这句话。
反正先假设 bb 存在，然后尝试去解它。
考虑解某个特殊的 i=ji=j 的 bjb_j。
G(x)=bj1−p(j)x+∑i=1,i≠jmbi1−p(i)xG(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)=bj+∑i=1,i≠jmbi1−p(j)x1−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=1p(j)x=\frac{1}{p(j)}，有 1−p(j)x=01-p(j)x=0，可以把那个 ∑\sum 消掉。
bj=(1−p(j)p(j))G(1p(j))b_j=(1-\frac{p(j)}{p(j)})G(\frac{1}{p(j)})
不能直接消成 bj=0×G(1p(j))=0b_j=0\times G(\frac{1}{p(j)})=0，因为 G(1p(j))G(\frac{1}{p(j)}) 代进去算的话会有一个项是 11−p(j)p(j)\frac{1}{1-\frac{p(j)}{p(j)}}，所以整个 G(1p(j))G(\frac{1}{p(j)}) 算出来是 ∞\infin，0×∞0\times \infin 没有定义。
形式化地说就是，G(x)G(x) 在 x=1p(j)x=\frac{1}{p(j)} 处有一个极点。
o3 说这里应该“用留数定理显式计算极限”，不过我不会高等的工具，所以我代入 G(x)G(x) 的定义式 ∏i=1m11−p(i)x\prod_{i=1}^m \frac{1}{1-p(i)x}。
bj=(1−p(j)p(j))∏i=1m11−p(i)p(j)b_j=(1-\frac{p(j)}{p(j)})\prod_{i=1}^m \frac{1}{1-\frac{p(i)}{p(j)}}
把 ∏\prod 里面 i=ji=j 的项摘出来消掉，这样就没有极点了，然后通分推一推。
bj=∏i=1,i≠jm11−p(i)p(j)=∏i=1,i≠jm1p(j)−p(i)p(j)=∏i=1,i≠jmp(j)p(j)−p(i)=p(j)m−1∏i=1,i≠jm1p(j)−p(i)\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)p(i) 的定义式。
bj=p(j)m−1∏i=1,i≠jm1p(j)−p(i)=p(j)m−1∏i=1,i≠jm1(uj+v)−(ui+v)=p(j)m−1∏i=1,i≠jm1u(j−i)=p(j)m−1um−1∏i=1,i≠jm1j−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}
考虑求 ∏i=1,i≠jm(j−i)\prod_{i=1,i\ne j}^m (j-i)，拆成 i<ji<j 和 i>ji>j 两个部分，前者的贡献是 (j−1)!(j-1)!，后者的贡献是 (−1)m−j(m−j)!(-1)^{m-j}(m-j)!。
bj=p(j)m−1um−1(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)=∑i=1mbi1−p(i)xG(x)=\sum_{i=1}^m \frac{b_i}{1-p(i)x}。
注意到根据经典式子（在原题中其实是先推出这个式子，然后再写成上面“题意”里的式子），11−p(i)x=∑k=0∞p(i)kxk\frac{1}{1-p(i)x}=\sum_{k=0}^{\infin}p(i)^kx^k，所以有
[xn]G(x)=∑i=1mp(i)m−1um−1(i−1)!(−1)m−i(m−i)!p(i)n=∑i=1mp(i)n+m−1um−1(i−1)!(−1)m−i(m−i)!\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}
时间复杂度 Θ(mlog⁡n)\Theta(m\log n)，空间复杂度 O(1)O(1)。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...