@[血色黄昏](/user/220426) 对998244353取模
by little_brush @ 2021-02-26 21:21:43
直接求不就是$O(n)$吗
by Liuyuzhuo @ 2021-02-26 21:35:39
@[Liuyuzhuo](/user/221575) 要求前 $n$ 项的每一项，直接求是$O(n^2)$吧
by zzr8178541919 @ 2021-02-26 21:38:01
我觉得我假了/kk
但这个思路会比n^2优
by w23c3c3 @ 2021-02-26 21:38:44
哦，我傻了
by Liuyuzhuo @ 2021-02-26 21:39:33
为什么我觉得这个柿子很像泰勒展开啊…
by 1saunoya @ 2021-02-26 21:39:54
首先分块，长度为 $B$ 分一块。
$F_t(x) = \sum\limits_{i = 0}^{tB} \frac{x^i}{i!}$
然后对于在 $((i - 1) B, i B]$ 的点多点求值，散块暴力
这样的复杂度是 $\Theta(n B + \frac{n}{B}(n \log n + B \log^2 B))$
也就是 $\Theta(n B + \frac{n^2}{B} \log n + n \log^2 B))$
$B$ 取到 $\sqrt{n \log n}$ 时最优，是 $\Theta(n \sqrt{n \log n} + n\log^2n)$
常数优秀一点就能过吧？
by zhoukangyang @ 2021-02-26 21:40:26
@[Isaunoya](/user/96580) 但哪个函数求一次导次方多一啊qwq
by 血色黄昏 @ 2021-02-26 21:41:24
@[Isaunoya](/user/96580) 我也觉得/fad
by VinstaG173 @ 2021-02-26 21:41:29
感觉我的做法好菜啊，有没有更优的做法啊 /kk
by zhoukangyang @ 2021-02-26 21:42:05