发布时间：2024-07-31

多项式开根a0!=1

需要检验a0是否有二次剩余，即$x^2 \equiv a_0(\mod 998244353)$是否成立

int cipolla(int x){
    if(qpow(x,P-1>>1)==P-1)return -1;
    while(1){
        int a=rng()%P;
        int w=(a*a%P-x+P)%P;
        auto mul=[&](PII a,PII b){
            return PII{(a.F*b.F%P+w*a.S%P*b.S%P)%P,(a.F*b.S%P+a.S*b.F%P)%P};
        };
        auto pow=[&](PII a,int b){
            PII res{1,0};
            for(;b;b>>=1){
                if(b&1)res=mul(res,a);
                a=mul(a,a);
            }
            return res.F;
        };
        if(qpow(w,P-1>>1)==P-1){
            int res=pow(PII{a,1},P+1>>1);
            return min(res,P-res);
        }
    }
}
// 多项式开根(a0!=1)
poly sqrt(const poly &f,int n){
    if(n==1){
        if(f[0]==1)return {1};
        return {cipolla(f[0])};
    }
    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;
}