RT

简单多项式开根。

若干月前写过这玩意，现在想写个循环版的（但是第二个样例意识过不去，然后好像每次前两项都是对的，后面就寄了。

有没有大佬给看看是什么原因啊QAQ

球球了QAQ

其中 NTT(f,n,t=0) 是对数组 f 的前 n 项 NTT,t 是看是正是逆。

IV(f,n,g) 是求 f 前 n 项的逆元存进 g 里。

这两个都过掉了板子，应该没啥问题。

下面是开根部分代码。

inline void sqrt(int *f,int n,int *g){
    int N=1;
    g[0]=1;
    while(N<n){
        N<<=1;
        for(int i=N;i<(N<<1);i++)t[i]=f[i],f[i]=0;
        IV(g,N,tmp);
        NTT(f,N<<1);
        NTT(tmp,N<<1);
        for(int i=0;i<N<<1;i++)
            tmp[i]=f[i]*tmp[i]%M;
        NTT(f,N<<1,1);
        NTT(tmp,N<<1,1);
        for(int i=0;i<N;i++)
            g[i]=(g[i]+tmp[i])*inv(2)%M;
        for(int i=0;i<N<<1;i++)tmp[i]=0;
        for(int i=N;i<(N<<1);i++)
            f[i]=t[i];
    }
    for(int i=0;i<N;i++)
        g[i]=(g[i]+M)%M;
}