发布时间：2024-07-31

多项式开根(a0=1)

给定一个 $n-1$ 次多项式 $A(x)$，求一个在 ${} \bmod x^n$ 意义下的多项式 $B(x)$，使得 $B^2(x) \equiv A(x) \pmod{x^n}$。若有多解，请取零次项系数较小的作为答案。

多项式的系数在 ${}\bmod 998244353$ 的意义下进行运算。

牛顿迭代法，构造式子$H(t)=t^2-F(x)$

带入式子得$G_1(x)=G_0(x)-\frac{G_0(x)^2-F(x)}{2G_0(x)}=\frac{G_0(x)^2+F(x)}{2G_0(x)}=\frac{1}{2}(G_0(x)+\frac{F(x)}{G_0(x)})$

poly sqrt(const poly &f,int n){
    if(n==1)return {1};
    auto g=sqrt(f,n+1>>1);
    static vector<int> c;
    static const int inv2=qpow(2,P-2);
    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;
    auto ig=inv(g,n);
    ntt(g,1),ntt(ig,1),ntt(c,1);
    for(int i=0;i<tot;i++)g[i]=(g[i]*g[i]%P+c[i])%P*ig[i]%P*inv2%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=sqrt(f,n+1);
    for(int i=0;i<n;i++)cout<<g[i]<<" ";
}