蒟蒻写题解实在不易

前置芝士

推式

推式中如有不理解的地方在多项式求逆的题解中均有详细说明

求\(B(x)\)，使得\(B(x)^2\equiv A(x)(mod x^n)\)

\[\begin{aligned}\\ B(x)^2\equiv A(x)(mod x^n),B(x)^2&\equiv A(x)(mod x^{\lceil\frac{n}{2}\rceil})\\ B(x)'^2&\equiv A(x)(mod x^{\lceil\frac{n}{2}\rceil})\\ B(x)^2-B'(x)^2&\equiv 0(mod x^{\lceil\frac{n}{2}\rceil})\\ B(x)^4+B'(x)^4-2B(x)^2B'(x)^2&\equiv 0(mod x^{\frac{n}{2}})\\ (B(x)^2+B'(x)^2)^2&\equiv (2B(x)B'(x))^2(mod x^{\frac{n}{2}})\\ B(x)^2+B'(x)^2&\equiv 2B(x)B'(x) (mod x^{\frac{n}{2}})\\ A(x)+B'(x)^2&\equiv 2B(x)B'(x)(mod x^{\frac{n}{2}})\\ B(x)&\equiv \frac{A(x)+B'(x)^2}{2B'(x)}(mod x^{\frac{n}{2}})\\ \end{aligned}\]

边界：\(n=1\longrightarrow (mod x)\)，则仅剩常数项，\(B_0=\sqrt{A_0}\)

至此，我们得到的最终的式子，仅需求逆就能实现开方了

code

细节：由于期间在求逆与开方间反复调换，要注意模的次数

#include
    
     typedef long long LL;const LL maxn=1e6+9,mod=998244353,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(1);    while(b){        if(b&1) ret=ret*base%mod; base=base*base%mod; b>>=1;    }return ret;}LL r[maxn];inline void NTT(LL *a,LL n,LL type){    for(LL i=0;i
     
      >1]>>1)|((i&1)<
      
       >1,A,B);    for(LL i=0;i
       
        >1,A,B);    LL n(deg+1>>1);    for(LL i=0;i