NFLSPC #2 Polynomial 题解

2019-11-28 22:58:41 By wzy

考虑第一次操作是 $(x+c)^k$,那么可以把最终的多项式表示成一个和 $x+c$ 有关的多项式,即计算:

$$g(x+c)=f(x),g(x)=f(x-c)$$

$$g(x)=\sum_{i=0}^{n-1}(x-c)^ia_{i}=\sum_{i=0}^{n-1}a_i\sum_{j=0}^ix^j(-c)^{i-j}\binom{i}{j}$$

交换求和顺序之后是一个卷积的形式,可以多项式乘法求出。

考虑如何计算 $c$,不难发现只需要考虑最高项和次高项的系数即可列方程解得 $c$,由于 $k>1$,因此每次非零系数的数量至少减半,可以压在一起处理。

总复杂度 $T(n)=T(n/2)+O(nlogn)=O(nlogn)$。

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。