问题:
给定一个多项式 \(F(x)\) ,请求出一个多项式 \(G(x)\), 满足 \(F(x) * G(x) \equiv 1 \pmod{x^n}\)。系数对 \(998244353\) 取模。
考虑分治,假设我们已经求出多项式 \(F(x)\) 在 \(\bmod x^{\lceil \frac{n}{2}\rceil}\) 时的逆 \(G'(x)\)。
有:
\[F(x)*G'(x)\equiv 1(\bmod x^{\lceil \frac{n}{2}\rceil})
\]
\[F(x)*G(x)\equiv 1(\bmod x^{\lceil \frac{n}{2}\rceil})
\]
即:
\[G(x)-G'(x)\equiv 0(\bmod x^{\lceil \frac{n}{2}\rceil})
\]
平方得:
\[(G(x)-G'(x))^2\equiv 0(\bmod x^{n})
\]
\[G(x)^2-2G(x)G'(x)+G'(x)^2\equiv 0(\bmod x^{n})
\]
\[G(x)-2G'(x)+F(x)G'(x)^2\equiv 0(\bmod x^{n})
\]
\[G(x)\equiv 2G'(x)-F(x)G'(x)^2(\bmod x^{n})
\]
因为 \(F(x)*G'(x)\equiv 1(\bmod x^{\lceil \frac{n}{2}\rceil})\),所以 \(G'\) 的 \(x^{t}\) 项的系数为 \(0\)(\(t\ge\lceil \frac{n}{2}\rceil\)),\(G(x)-G'(x)\) 的 \(x^{t}\) 项的系数为 \(0\)(\(0<t<\lceil \frac{n}{2}\rceil\)),所以 \((G(x)-G'(x))^2\equiv 0(\bmod x^{n})\) 成立。
Code:
LL X[N],Y[N];
// 多项式乘法
void Mul(LL *a,LL *b,LL *c,LL _n,LL _m){
int Len=1;while(Len<=(_n+_m+2))Len<<=1;
for(int i=0;i<Len;i++)X[i]=Y[i]=0;
for(int i=0;i<_n;i++)X[i]=a[i];
for(int i=0;i<_m;i++)Y[i]=b[i];
NTT(X,Len,0),NTT(Y,Len,0);
for(int i=0;i<Len;i++)X[i]=X[i]*Y[i]%mo;
NTT(X,Len,1);
for(int i=0;i<_n+_m-1;i++)c[i]=X[i];
}
// 多项式乘法逆
LL INV[N],P[N];
void Poly_Inv(LL *a,LL n){
if(n==1){INV[0]=ksm(a[0]);return;}
int m=(n+1)>>1;Poly_Inv(a,m);
Mul(INV,INV,P,m,m),Mul(P,a,P,n,n);
for(int i=0;i<n;i++)INV[i]=(2ll*INV[i]%mo-P[i]+mo)%mo;
}