这不[多项式复合](https://www.luogu.com.cn/problem/P5373)吗
by Hank_2007 @ 2024-03-28 21:19:02
@[Hank_2007](/user/210137) 有没有简单点的做法
by Lgx_Q @ 2024-03-28 21:20:15
感觉不太能有
by Hank_2007 @ 2024-03-28 21:21:44
@[Lgx_Q](/user/375953) [P8486 「HGOI-1」Competition](https://www.luogu.com.cn/problem/P8486)
by 飞雨烟雁 @ 2024-03-28 21:23:58
是不是 $F(x)=\sum_i f_i x^i,F(e^x)=\sum_i f_i \sum_j \frac{i^jx^j}{j!}$,假如我们忽略 $j!$ 那么就是 $\sum \frac{f_i}{1-ix}$
by syzf2222 @ 2024-03-28 21:24:33
是不是有一道题叫做猎人就是差不多这个形式啊,记得好像是分治。
by syzf2222 @ 2024-03-28 21:25:45
@[syzf2222](/user/140876) 这个式子怎么算?
by Lgx_Q @ 2024-03-28 21:25:58
@[Lgx_Q](/user/375953) 更简单的做法:
$$F(\text e^x)=\sum_{i=0}^nf_i \text e^{ix}=\sum_{j=0}^\infty \frac{x^j}{j!}\sum_{i=0}^n f_i i^j$$
可以考虑计算
$$\sum_{j=0}^\infty x^j\sum_{i=0}^n f_i i^j=\sum_{i=0}^n \frac{f_i}{1-ix}$$
分治计算,维护 $P(x)/Q(x)$ 形式的分式即可。
by NaCly_Fish @ 2024-03-28 21:26:04
就是分治吧,维护一下分子分母就好了
by syzf2222 @ 2024-03-28 21:26:59
@[NaCly_Fish](/user/115864) @[syzf2222](/user/140876)
懂了,感谢
by Lgx_Q @ 2024-03-28 21:28:32