【learning】多项式相关（求逆、开根、除法、取模）

（⾸先要%miskcoo，实在是太强啦qwq⼤部分多项式相关的知识都是从这位dalao博客⾥⾯学的，作为⼀只蒟蒻还是疯狂膜拜后⾃⼰理下思路吧qwq）

多项式求逆（元）

定义

　　对于⼀个多项式A(x)，如果存在⼀个多项式B(x)，满⾜B(x)的次数⼩于等于A(x)且A(x)B(x)\\equiv 1(mod\\ x^n)，那么我们称B(x)为A(x)在模x^n意义下的逆元，简单记作A^{-1}(x)

求解

　　从最简单的情况开始考虑，当n=1的时候A(x)\\equiv\\ c\\ (mod\\ x)，c为A(x)的常数项，此时A^{-1}(x)为c的逆元　　在这个基础上我们继续考虑⼀般情况

　　对于n>1的情况，不妨设B(x)=A^{-1}(x)，那么我们可以根据定义列出下⾯的式⼦：A(x)B(x)\\equiv 1(mod\\ x^n)

　　这⾥的话考虑⽤倍增的⽅式求解（算倍增吧），这⾥假设我们已经知道了A(x)在mod\\ x^{\\lceil \\frac{n}{2} \\rceil}下的逆元G(x)，那么有：A(x)G(x)\\equiv 1(mod\\ x^{\\lceil \\frac{n}{2} \\rceil})

　　我们把A(x)和B(x)的式⼦写成mod\\ x^{\\lceil \\frac{n}{2} \\rceil}下的：

　　（可以这么写是因为mod\\ x^n相当于将乘积中x次数⼤于等于n的忽略掉了，⽽mod\\ x^{\\lceil \\frac{n}{2} \\rceil}则相当于忽略了更多的项，既然前者满⾜，那么后者肯定也满⾜）

A(x)B(x)\\equiv 1 (mod\\ x^{\\lceil \\frac{n}{2} \\rceil})　　把这两条式⼦相减，就可以搞事情了：

\\begin{aligned} A(x)[B(x)-G(x)]&\\equiv 0\\ (mod\\ x^{\\lceil \\frac{n}{2} \\rceil})\\\\ B(x)-G(x)&\\equiv 0\\ (mod\\ x^{\\lceil \\frac{n}{2} \\rceil})\\\\ \\end{aligned}　　然后我们两边平⽅⼀下：

B^2(x)-2B(x)G(x)+G^2(x)\\equiv 0\\ (mod\\ x^{\\lceil \\frac{n}{2} \\rceil})

　　然后这⾥有个很神奇的事情，B(x)-G(x) 在mod\\ x^{\\lceil \\frac{n}{2} \\rceil}下为0，说明这个式⼦最后的结果的0到\\lceil \\frac{n}{2} \\rceil -1次项系数都为0，平⽅了之后，对于结果的i次项系数，（0<=i<=2*\\lceil \\frac{n}{2} \\rceil -1 ），其系数a_i = \\sum\\limits_{j=0}^{i}a_j a_{i-j}，⽽a_j和a_{i-j}中必定有⼀项为0（因为j和i-j中必定有⼀个值⼩于\\lceil \\frac{n}{2} \\rceil），所以我们可以得到⼀个结论，这个式⼦在平⽅了之后在mod \\ x^n下也是0　　那么我们就可以写成：

\\begin{aligned} B^2(x)-2B(x)G(x)+G^2(x)&\\equiv 0\\ (mod\\ x^n)\\\\ A(x)B(x)*B(x)-2*A(x)B(x)*G(x)+A(x)G^2(x)&\\equiv 0\\ (mod\\ x^n)\\\\\\end{aligned}

　　两边同时乘上A(x)，由逆元的定义我们可以将上⾯的式⼦化简成下⾯这样：B(x)-2G(x)+A(x)G^2(x)\\equiv 0\\ (mod\\ x^n)　　最后得到：

B(x)\\equiv 2G(x)-A(x)G^2(x)\\ (mod\\ x^n)

　　也就是说，如果我们知道G(x)，我们就可以推出B(x)了

　　具体的实现可以⽤递归的⽅式实现，中间的多项式乘法可以⽤fft加速⼀下，那么最终的时间复杂度就是T(n)=T(\\frac{n}{2})+O(n \\ log\\ n)=O(n\\ log \\ n)

　　然⽽为啥这样搞完了还是⼀个log呢？因为每次递归下去多项式的最⾼次数都会减半，稍微算⼀下就会发现最后总的时间复杂度合起来还是⼀个log⽽不是两个

　　注意，后⾯这⼀堆推式⼦的过程是建⽴在n=1的时候有解的前提下的，所以我们还可以得到⼀个结论：⼀个多项式在mod\\ x^n下是否有逆元取决于其常数项在mod \\ x^n下是否有逆元

实现

　　⾸先先实现⼀个namespace NTT，然后除了基础的函数外主要供外部调⽤的过程是这个：

void Ntt_getinv(vct &a,vct &b,int n,int m){

prework(a,b,n,2*m);//这⾥注意因为后⾯是A*B*B，所以m要*2 ntt(A,1); ntt(B,1);

for (int i=0;iB[i]=(2LL-1LL*A[i]*B[i]%MOD+MOD)*1LL*B[i]%MOD; ntt(B,-1);}

　　然后求逆的过程⼤概是这样（这⾥⽤vector来写了）：

vct Inv(vct a){ int N=a.size(); if (N==1){

a[0]=ksm(a[0],MOD-2); return a; }

vct b=a; b.resize((N+1)>>1); b=Inv(b); b.resize(N); NTT::Ntt_getinv(a,b,N,N); b.resize(NTT::len);

for (int i=0;i　　求逆⼤概就是这样吧ovo　　

多项式开根

定义

　　对于⼀个多项式A(x)，如果存在⼀个多项式B(x)，满⾜B^2(x)\\equiv\\ A(x) (mod\\ x^n)，则称B(x)为A(x)在mod\\ x^n下的平⽅根

求解

　　同样是考虑最简单的情况，当n=0的时候，B(x)的常数项就是1　　然后考虑⼀般情况，同样的思路，考虑⽤倍增的⽅式来求

　　假设我们已经知道了A(x)在mod\\ x^{n}下的平⽅根G(x)，现在要求在mod\\ x^{2n}下的平⽅根B(x)，根据定义我们可以列出式⼦：\\begin{aligned} B^2(x)&\\equiv A(x)(mod\\ x^{2n})\\\\ G^2(x)&\\equiv A(x)(mod\\ x^n) \\end{aligned}　　我们对这个式⼦进⾏⼀些处理：

\\begin{aligned} G^2(x)&\\equiv A(x)(mod\\ x^n)\\\\ G^2(x)-A(x)&\\equiv 0(mod\\ x^n)\\\\ \\end{aligned}　　那么可以得到（因为右边是0所以可以这么搞）：

\\begin{aligned} (G^2(x)-A(x))^2&\\equiv 0 (mod\\ x^{2n})\\\\ G^4(x)-2G^2(x)A(x)+A^2(x)&\\equiv 0(mod\\ x^{2n})\\\\ \\end{aligned}　　然后两边加上4G^2(x)A(x)：

\\begin{aligned} G^4(x)+2G^2(x)A(x)+A^2(x)&\\equiv 4G^2(x)A(x)(mod\\ x^{2n})\\\\ (G^2(x)+A(x))^2&\\equiv 4G^2(x)A(x)(mod\\ x^{2n})\\\\(G^2(x)+A(x))^2&\\equiv (2G(x))^2A(x)(mod\\ x^{2n})\\\\ \\end{aligned}　　我们将(2G^2(x))^2移到左边去，将左边写成⼀个平⽅的形式，得到：(\\frac{G^2(x)+A(x)}{2G(x)})^2\\equiv A(x)(mod\\ x^{2n})　　等式左边的东西就是我们要求的B(x)

　　所以如果说我们知道了G(x)，我们也就可以得出B(x)啦，分母可以⽤多项式求逆搞⼀下，其他的多项式乘法fft搞⼀下，问题不⼤　　总的复杂度是：

T(n)=T(\\frac{n}{2})+求逆复杂度+O(n\\ log \\ n)=O(n\\ log\\ n)　　

实现

　　namespace NTT中主要需要调⽤的过程长这个样⼦

void Ntt_getsqrt(vct &a,vct &invb,int n,int m){ prework(a,invb,n,m); ntt(A,1); ntt(B,1);

for (int i=0;iB[i]=1LL*B[i]*inv2%MOD*A[i]%MOD; ntt(B,-1);}

　　开根的话⼤概长这个样⼦

vct Sqrt(vct a){

int N=a.size(),M,M1; if (N==1){ a[0]=1; return a; }

vct b=a,invb;

b.resize((N+1)>>1); b=Sqrt(b);

invb=b; invb.resize(N);//resize invb=Inv(invb);

NTT::Ntt_getsqrt(a,invb,N,N); b.resize(NTT::len);

for (int i=0;i　　　　　　

多项式除法

问题

　　给出⼀个n次多项式A(x)，以及⼀个（m（m<=n)次多项式B(x)

　　要求出D(x)满⾜A(x)=D(x)B(x)+R(x)，且D(x)的次数<=n-m，R(x)的次数求解

　　为了⽅便接下来的表述，先定义⼀些操作，我们记：rev(A(x))=x^nA(\\frac{1}{n})

　　也就是系数反转，举个简单的例⼦：

\\begin{aligned} A(x)&=4x^4+3x^3+2x^2+1\\\\ rev(A(x))&=x^4+2x^3+3x^2+4 \\end{aligned}　　那么现在我们把上⾯那条式⼦搬下来：A(x)=D(x)B(x)+R(x)

　　（接下来的步骤均将D(x)看成n-m次多项式，R(x)看成m-1次多项式，对于那些不存在的⾼次项我们就把系数看成0就好了）　　后⾯的余数看起来⼗分不友善，所以我们要想个办法把它去掉，于是我们可以进⾏以下的操作:　　我们将上⾯式⼦中的所有x换成\\frac{1}{x}，然后等式两边同时乘上x^n，得到：

\\begin{aligned} x^nA(\\frac{1}{x})&=x^{n-m}D(\\frac{1}{x})x^mB(\\frac{1}{x})+x^{n-m+1}x^{m-1}R(\\frac{1}{x})\\\\rev(A(x))&=rev(D(x))rev(B(x))+x^{n-m+1}rev(R(x))\\\\ \\end{aligned}

　　现在再来看⼀下各个项的最⾼次项，⾸先是我们要求的元素D(x)，由于这个多项式原来是n-m次，所以在系数反转之后肯定不会超过n-m次，⽽我们要“消掉”的R(x)原来是m-1次多项式，所以x^{n-m+1}R(x)的最低次项应该是⼤于n-m 的

　　那么考虑将上⾯的式⼦放到mod\\ x^{n-m+1}下，x^{n-m+1}R(x)的影响就可以⼗分愉快滴被消掉啦，同时我们也不会影响到D(x)的求解，因为D(x)是n-m次的（疯狂%miskcoo太强了qwq）　　于是我们就得到了这样⼀个式⼦：

rev(A(x))\\equiv\\ rev(D(x))rev(B(x))\\ (mod\\ x^{n-m+1})

　　那所以，我们只要求⼀个rev(B(x))在mod x^{n-m+1}意义下的逆元然后跟rev(A(x))乘⼀下，得到rev(D(x))，然后再把系数反转回来就得

到D(x)啦

实现

　　除法⼤概是长这个样⼦

vct operator / (vct a,vct b){ int N=a.size()-1,M=b.size()-1; if (Nd.resize(1);d[0]=0; return d; }

reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); b.resize(N-M+1); d=Inv_p(b)*a; d.resize(N-M+1);

reverse(d.begin(),d.end()); return d;}

多项式取模

问题

　　 这个。。其实就是求上⾯那个R(x)

求解

　　有了多项式除法（也就是求商）之后，求余数就变得⽐较简单了

　　类⽐整数的取模，我们可以得到这样的⼀个式⼦：R(x)=A(x)-D(x)B(x)

　　那就除法求出D(x)之后直接减⼀下就好了，D(x)B(x)这个多项式乘法也是直接⽤fft求就好了

实现

　　假装⾮常短的样⼦ (然⽽前⾯的东西都是要写的qwq醒醒)

void mod(vct &a,vct b){

int N=a.size()-1,M=b.size()-1; if (N　

　　⼤概。。就先写这么多吧ovo

Processing math: 0%