多项式求逆

\[A\times B\equiv 1(\mod x^n)\\ A\times B'\equiv 1(\mod x^{\frac n 2}) \]

那么

\[B-B'\equiv0(\mod x^{\frac n 2})\\ (B-B')^2\equiv0 (\mod x^n)\\ B^2-2BB'+B'^2\equiv0(\mod x^n) \]

同乘 \(A\)，得

\[AB^2-2ABB'+AB'^2\equiv0(\mod x^n)\\ B-2B'+AB'^2\equiv0(\mod x^n)\\ B\equiv B'(2-AB')(\mod x^n) \]

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
inline ll poww(ll x,int k,int mod)
{
	ll res=1;
	while(k)
	{
		if(k&1) res=1ll*res*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return res;
}
const int mod=998244353,G=3,invG=poww(G,mod-2,mod),N=(1e5+9)*20;
ll f[N],g[N],t[N];
int n,r[N],lim,len;

inline void NTT(ll *f,int lim,int op)
{
	for(int i=0;i<lim;i++) if(i<r[i]) swap(f[i],f[r[i]]);
	for(int mid=1;mid<lim;mid<<=1)
	{
		ll Wn=poww(op==1?G:invG,(mod-1)/(mid<<1),mod);
		for(int i=0;i<lim;i+=(mid<<1))
		{
			ll w=1;
			for(int k=0;k<mid;k++,w=(w*Wn)%mod)
			{
				ll x=f[i+k],y=f[i+k+mid]*w%mod;
				f[i+k]=(x+y)%mod;
				f[i+k+mid]=(x-y+mod)%mod;
			}
		}
	}
	if(op==1) return;
	ll inv=poww(lim,mod-2,mod);
	for(int i=0;i<lim;i++)
		f[i]=f[i]*inv%mod;
}

void solve(ll *f,ll *g,int len)
{
	if(len==1){g[0]=poww(f[0],mod-2,mod);return;}
	solve(f,g,(len+1)>>1);
	int l=0,lim=1;
	while(lim<(len<<1)) lim<<=1,++l;
	for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	memset(t,0,sizeof t);
	for(int i=0;i<len;i++) t[i]=f[i];
	NTT(t,lim,1),NTT(g,lim,1);
	for(int i=0;i<lim;i++) g[i]=(2ll-t[i]*g[i]%mod+mod)%mod*g[i]%mod;
	NTT(g,lim,-1);
	for(int i=len;i<lim;i++) g[i]=0;
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%lld",&f[i]);
	solve(f,g,n); 
	for(int i=0;i< n;i++) printf("%lld ",g[i]);
	return 0;
}