题目概述

给出一个多项式 $A(x)$ ，求 $B(x)$ 使得 $B^2(x)\equiv A(x)(mod\ x^n)$ ，保证 $A(x)_0=1$ 。

解题报告

前置姿势：多项式求逆。还是考虑倍增：

$$ G^2(x)\equiv A(x)(mod\ x^n)\\ G^2(x)-A(x)\equiv 0(mod\ x^n)\\ G^4(x)-2G^2(x)A(x)+A^2(x)\equiv 0(mod\ x^{2n})\\ G^4(x)+2G^2(x)A(x)+A^2(x)\equiv 4G^2(x)A(x)(mod\ x^{2n})\\ \lbrack G^2(x)+A(x)\rbrack^2\equiv 4G^2(x)A(x)(mod\ x^{2n})\\ \lbrack{G^2(x)+A(x)\over 2G(x)}\rbrack^2\equiv A(x)(mod\ x^{2n})\\ $$

就可以得到 $B(x)=2^{-1}[G(x)+A(x)G^{-1}(x)](mod\ 998244353)$ 了。

$n=1$ 的时候 $B(x)_0\equiv\sqrt{A(x)_0}(mod\ 998244353)$ ，二次剩余我不会啊，反正保证了 $A(x)_0=1$ QAQ。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=262144,MOD=998244353,INV2=MOD+1>>1;

int n,m,a[maxn+5],b[maxn+5],B[maxn+5],C[maxn+5],rev[maxn+5],pw[2][maxn+5];

inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                x=a[i+j],y=(LL)a[i+j+k]*g%MOD,AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);
    }if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=(LL)a[i]*INV%MOD;
}
void Inv(int *a,int *b,int n){
    if (n==1) {b[0]=Pow(a[0],MOD-2);return;}Inv(a,b,n>>1);Pre(n<<1);
    for (int i=0;i<n;i++) B[i]=a[i],B[i+n]=b[i+n]=0;NTT(B,n<<1,1);NTT(b,n<<1,1);
    for (int i=0;i<(n<<1);i++) B[i]=(LL)b[i]*(2+MOD-(LL)B[i]*b[i]%MOD)%MOD;
    NTT(B,n<<1,-1);for (int i=0;i<n;i++) b[i]=B[i],b[i+n]=0;
}
void Sqrt(int *a,int *b,int n){
    if (n==1) {b[0]=1;return;}Sqrt(a,b,n>>1);Pre(n<<1);Inv(b,C,n);
    for (int i=0;i<n;i++) B[i]=a[i],B[i+n]=0;NTT(B,n<<1,1);NTT(C,n<<1,1);
    for (int i=0;i<(n<<1);i++) B[i]=(LL)B[i]*C[i]%MOD;
    NTT(B,n<<1,-1);for (int i=0;i<n;i++) b[i]=(LL)(b[i]+B[i])*INV2%MOD;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&m);for (int i=0;i<m;i++) scanf("%d",&a[i]);for (n=1;n<m;n<<=1);Sqrt(a,b,n);
    for (int i=0;i<m;i++) i?putchar(' '):0,printf("%d",b[i]);puts("");return 0;
}