自然数幂和的一个问题

学术版

wishapig @ 2023-01-31 19:20:06

给出 a_{1\cdots n},c_{1\cdots n}：

\sum_{i=1}^n\dfrac{c_i}{1-a_ix}

1\le a_i,c_i< 998244353

这个东西有快速的做法吗？

by NaCly_Fish @ 2023-01-31 19:34:10

@wishapig 是求这玩意的前 m 项系数吗？如果是的话，\Theta(n \log^2 n) 算快速做法吗？

by masterhuang @ 2023-01-31 19:40:59

@wishapig 目前科技最好是 n\log ^2 n 的吧

by jijidawang @ 2023-01-31 20:02:20

@NaCly_Fish 咋做到和 m 无关的，能不用求逆？

by NaCly_Fish @ 2023-01-31 21:20:13

@wishapig 维护 i \in [l,r] 的项加起来的分子和分母，然后合并的时候就是

\frac{F(x)}{G(x)}+\frac{P(x)}{Q(x)}= \frac{F(x)Q(x)+P(x)G(x)}{G(x)Q(x)}

时间复杂度我是直接默认 n,m 同阶了

by wishapig @ 2023-01-31 21:21:26

@NaCly_Fish wssb！