【模板】多项式求逆

蒟蒻写题解实在不易

前置芝士

多项式最高次数为度，多项式(A)的度记为：(deg(A))

多项式取模的意义：将多项式(A)记作余式(A(x)=Q(x)B(x)+R(x))，则(A(x)equiv R(x)(mod~B(x)))

在有模数(mod)的情况下，(F(x)G(x)equiv 1 (mod~x^n))的具体情况：(F(x)G(x))后次数(≥n)的不管，其他除常数项为(1)外其他项系数除(mod)后为0

推式前置

(F(x)G(x)equiv 1 (mod~x^n))；(F(x)G(x)=Q(x)*x^n+1)
求逆的关键在于(G(x))由(F(x)H(x)equiv 1(mod~ x^{lceil frac{n}{2} ceil}))的(H(x))推过来
当(F(x)G(x)equiv 1 (mod~x))则除常数项其他是会消掉的，(F(x)equiv f[0] (mod~x))，( herefore G(x)=f[0]^{-1})
那么(G(x))与(H(x))有什么关系呢？先看一下((mod~x^n))与((mod~ x^{lceil frac{n}{2} ceil})(n>1))的关系：

[egin{aligned}\ F(x)G(x)&=Q*x^n+1\ F(x)G(x)&=Q'*x^{lceil frac{n}{2} ceil}+?\ ?=1：Q'&可以通过与Q的相乘次数差转换过来，所以余数为1\ end{aligned}]

(F(x)G(x)equiv 1(mod~x)longrightarrow F(x)G(x)equiv 1(mod~ x^{lceil frac{n}{2} ceil}))
事实上，我们能得到：$$A(x)equiv R(x)(mod~x^n)longrightarrow A(x)equiv R(x)(mod ~x^{lceil frac{n}{2} ceil})$$

推式

[egin{aligned}\ F(x)G(x)&equiv 1(mod~x^n)\ F(x)H(x)&equiv 1(mod~ x^{lceil frac{n}{2} ceil}),F(x)G(x)equiv 1(mod~ x^{lceil frac{n}{2} ceil})\ F(x)(G(x)-H(x))&equiv 0(mod~ x^{lceil frac{n}{2} ceil})\ G(x)-H(x)&equiv 0(mod~ x^{lceil frac{n}{2} ceil})\ (G(x)-H(x))^2&equiv 0(mod~x^n)\ G(x)^2-2G(x)H(x)+H(x)^2&equiv 0(mod~x^n)\ F(x)(G(x)^2-2G(x)H(x)+H(x)^2)&equiv 0 (mod~x^n)\ F(x)G(x)cdot G(x)-(F(x)G(x)cdot 2H(x)+(F(x)H(x)^2&equiv 0(mod~x^n)\ G(x)-2H(x)+F(x)H(x)^2&equiv 0(mod~x^n)\ G(x)&equiv 2H(x)-F(x)H(x)^2(mod~x^n)\ end{aligned}]

具体实现

我们可以至底(x^1)向上求出(H(x))在更新至(G(x))，反复操作

由于次数在模意义的下次数较大时会消掉，所以我们并不需要每次都(NTT(x))

忽略常数及栈空间，递归求解感觉更舒服

code

#include<bits/stdc++.h>
typedef long long LL;
const LL mod=998244353,maxn=1e6+9,g=3;
inline LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1; c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3)+(x<<1)+c-'0'; c=getchar();
	}
	return x*f;
}
inline LL Pow(LL base,LL b){
	LL ret(1ll);
	while(b){
		if(b&1) ret=ret*base%mod;
		base=base*base%mod; b>>=1;
	}
	return ret;
}
LL r[maxn];
inline LL NTT(LL *a,LL n,LL type){
	for(LL i=0;i<n;++i) if(i<r[i]) std::swap(a[i],a[r[i]]);
	for(LL mid=1;mid<n;mid<<=1){
		LL wn(Pow(g,(mod-1)/(mid<<1)));
		if(type==-1) wn=Pow(wn,mod-2);
		for(LL R=mid<<1,j=0;j<n;j+=R){
			LL w(1);
			for(LL k=0;k<mid;++k,w=w*wn%mod){
                LL x(a[j+k]),y(w*a[j+mid+k]%mod);
				a[j+k]=(x+y)%mod; a[j+mid+k]=(x-y+mod)%mod;
			}
		}
	}
}
LL a[maxn],F[maxn],b[maxn];
void Solve(LL n,LL *G){
	if(n==1){
		G[0]=Pow(a[0],mod-2); return;
	}
	Solve(n+1>>1,G);
	LL limit(1),len(0);
	while(limit<(n<<1)){
		limit<<=1; ++len;
	}
	for(LL i=1;i<limit;++i) r[i]=(r[i>>1]>>1)|((i&1)<<len-1);
	for(LL i=0;i<n;++i) F[i]=a[i];
	for(LL i=n;i<limit;++i) F[i]=0;
    NTT(G,limit,1); NTT(F,limit,1);
	for(LL i=0;i<limit;++i)
		G[i]=(2ll-F[i]*G[i]%mod+mod)%mod*G[i]%mod;
	NTT(G,limit,-1);
	for(LL i=0;i<limit;++i)
		G[i]=G[i]*Pow(limit,mod-2)%mod;
	for(LL i=n;i<limit;++i) G[i]=0;
}
int main(){
    LL n(Read());
	for(LL i=0;i<n;++i) a[i]=Read();
	Solve(n,b);
	for(LL i=0;i<n;++i) printf("%lld ",b[i]);
	return 0;
}