【模板】多项式除法

2019-04-13 16:43发布

站内文章 / 模拟电子
14812 0 1043
class="markdown_views prism-atelier-sulphurpool-light"> 传送门:洛谷：【模板】多项式除法

题意

给定一个 n" role="presentation" style="position: relative;">n 次多项式 F(x)" role="presentation" style="position: relative;">F(x) 和一个 m" role="presentation" style="position: relative;">m 次多项式 G(x)" role="presentation" style="position: relative;">G(x) ，请求出多项式 Q(x)" role="presentation" style="position: relative;">Q(x) , R(x)" role="presentation" style="position: relative;">R(x) ，满足以下条件：
Q(x)" role="presentation" style="position: relative;">Q(x) 次数为 n−m" role="presentation" style="position: relative;">n−m， R(x)" role="presentation" style="position: relative;">R(x) 次数小于 m" role="presentation" style="position: relative;">m
F(x)=Q(x)×G(x)+R(x)" role="presentation" style="position: relative;">F(x)=Q(x)×G(x)+R(x)
所有的运算在模 998244353" role="presentation" style="position: relative;">998244353 意义下进行。

题解

由F(x)=Q(x)×G(x)+R(x) (mod xn+1)" role="presentation" style="position: relative;">F(x)=Q(x)×G(x)+R(x) (mod xn+1)
得F(1x)=Q(1x)×G(1x)+R(1x) (mod xn+1)" role="presentation" style="position: relative;">F(1x)=Q(1x)×G(1x)+R(1x) (mod xn+1)
同乘上一个xn" role="presentation" style="position: relative;">xn即Frev(x)=Qrev(x)×Grev(x)+Rrev(x)xn−degR (mod xn+1)" role="presentation" style="position: relative;">Frev(x)=Qrev(x)×Grev(x)+Rrev(x)xn−degR (mod xn+1)
其中Frev(x)" role="presentation" style="position: relative;">Frev(x)表示将多项式F(x)" role="presentation" style="position: relative;">F(x)的0,1...n" role="presentation" style="position: relative;">0,1...n次项的系数翻转。degR" role="presentation" style="position: relative;">degR表示R" role="presentation" style="position: relative;">R的次数。
因为degR<m" role="presentation" style="position: relative;">degR<m，显然n−degR>n−m" role="presentation" style="position: relative;">n−degR>n−m。而degQ=n−m" role="presentation" style="position: relative;">degQ=n−m
那么在mod n−m+1" role="presentation" style="position: relative;">