多项式求逆

多项式求逆指的是给定一个多项式\(F(x)\)，求出一个多项式\(G(x)\)满足

\[F(x)*G(x)\equiv1\pmod {x^n} \]

它是怎么做的？

我们称一个多项式的“度”为其最高次项系数\(+1\)

首先，我们知道当\(n=1\)的时候，显然\(G(x)\)即为\(F(x)\)的常数项之逆元

我们将原式写成模\(x^{\lceil\frac n 2\rceil}\)意义下的形式：

\[F(x)*G(x)\equiv1\pmod {x^{\lceil\frac n 2\rceil}} \]

假设我们已经求出\(B(x)\)满足

\[F(x)*B(x)\equiv1\pmod {x^{\lceil\frac n 2\rceil}} \]

将两个式子相减

\[G(x)-B(x)\equiv0\pmod{x^{\lceil\frac n 2\rceil}} \]

平方一下

\[G^2(x)-2G(x)B(x)+B^2(x)\equiv0\pmod{x^n} \]

两边乘上\(F(x)\)

\[G(x)-2B(x)+F(x)B^2(x)\equiv0\pmod{x^n} \]

（这里由于\(F(x)*G(x)\equiv1\pmod{x^n}\)，消去了一些部分）

移项整理得

\[G(x)\equiv(2-F(x)B(x))B(x)\pmod{x^n} \]

多项式乘法可以用FFT/NTT加速

Code

#include 
#include 
#include 
#include 
#include 
#include 
#define inv(x) (fastpow((x),mod-2))
using namespace std;
typedef long long ll;

template void read(T &t)
{
	t=0;int f=0;char c=getchar();
	while(!isdigit(c)){f|=c=='-';c=getchar();}
	while(isdigit(c)){t=t*10+c-'0';c=getchar();}
	if(f)t=-t;
}

const ll mod=998244353,gg=3,ig=332748118;
const int maxn=100000+5;
int n;
ll a[maxn<<2],b[maxn<<2];

ll fastpow(ll a,ll b)
{
	ll re=1,base=a;
	while(b)
	{
		if(b&1)
			re=re*base%mod;
		base=base*base%mod;
		b>>=1;
	}
	return re;
}

int len;
int r[maxn<<2];
void NTT(ll *f,int type)
{
	for(register int i=0;i>1;
		ll unr=fastpow(type?gg:ig,(mod-1)/p);
		for(register int l=0;l>1,a,b);
	for(len=1;len<=(deg<<1);len<<=1);
	for(register int i=0;i>1]>>1)|((i&1)?len>>1:0);
		c[i]=(i