发布时间：2024-07-31

多项式乘法逆

给定一个多项式 $F(x)$ ，请求出一个多项式 $G(x)$ ，满足 $F(x) * G(x) \equiv 1 \pmod{x^n}$ 。系数对 $998244353$ 取模。

牛顿迭代法已知一个复合多项式 $G(F(x)) \equiv 0(\mod x^n)$ ，假设 $F_0(x) \equiv F(x)(\mod x^{\frac{n}{2}}),F_1(x) \equiv F(x)(\mod x^n)$

泰勒公式在 $F_0(x)$ 展开 $G(F(x))$ , $G(F(x))=\sum_{i=0}^{\infty}\frac{G^{(i)}F_0(x)}{i!}(F(x)-F_0(x))^i$

$G(F_1(x)) \equiv G(F_0(x))+G'(F_0(x))(F_1(x)-F_0(x))(\mod x^n)$

$F_1(x)=F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}$

将 $H(t)=F(x)-\frac{1}{t}$ 套进去

$G_1(x)=G_0(x)-\frac{F(x)-\frac{1}{G_0(x)}}{\frac{1}{G_0(x)^2}}$

$G_1(x)=G_0(x)(2-G_0(x)F(x))$

cpp

poly inv(poly &f,int n){
    if(n==1)return {qpow(f[0],P-2)};
    auto g=inv(f,n+1>>1);
    static vector<int> c;
    init(2*n+1);
    c.resize(tot);
    g.resize(tot);
    for(int i=0;i<n;i++)c[i]=f[i];
    for(int i=n;i<tot;i++)c[i]=0;
    ntt(c,1),ntt(g,1);
    for(int i=0;i<tot;i++)g[i]=g[i]*(2-c[i]*g[i]%P+P)%P;
    ntt(g,-1);
    for(int i=n;i<tot;i++)g[i]=0;
    return g;
}
void solve(){
    int n;
    cin>>n;
    poly f(n+1);
    for(int i=0;i<n;i++)cin>>f[i];
    auto g=inv(f,n);
    for(int i=0;i<n;i++)cout<<g[i]<<" ";
}

多项式乘法逆 ​

多项式乘法逆