求助

回复帖子

@体育王子 2020-06-29 22:03 回复

可以得到 $k$ 取遍 $[1,10^5]$ 的所有

$$ \left(\sum_{i=1}^n a_ib_i^k\right) \bmod 998244353 $$

吗?其中 $n\le 10^5, 0\le a_i,b_i<998244353$。

@体育王子 2020-06-29 22:10 回复 举报

如果 $a_i=1$ 此题具有 $O(n\log^2 n)$ 做法:

$$ \sum_{k\ge 0} x^k \sum_{i=1}^n b_i^k=\sum_{i=1}^n \ln' (1-b_ix)=\ln'\left(\prod_{i=1}^n (1-b_ix)\right)$$

但在此题下这个做法显得无力。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。