小品：Bostan-Mori

· · 算法·理论

水一下水一下。

老规矩不会学习任何多项式相关内容。

求

[x^k]\frac{P(x)}{Q(x)}

方法是同乘 Q(-x)，然后分式

[x^k]\frac{P(x)Q(-x)}{Q(x)Q(-x)}=[x^k]\frac{F_0(x^2)}{G(x^2)}+x\frac{F_1(x^2)}{G(x^2)}

可以往一侧递归。

复杂度 f(n)\log k，其中 f(n) 是多项式卷积复杂度，我们是暴力多项式所以复杂度是 O(n^2\log k)。

例题：P17080 「Miku × Nene」共鸣序列。

由题意得答案为

pq[x^n]\frac{(a+(b-pa)x)^2}{(1-x)(1-px-qx^2)^2}

暴力提取系数即可。多项式大小视为常数。

太球鸡儿卡常了，需要卡常代码的可以找我。