Polynomial open root

For those to be rooted H(x), Find the root G(x)

The derivation process is as follows , about hereinafter referred to as k

Asking for is G(X)

And

So we ask for H(x) Inverse element ,2 Inverse element

# include<iostream>
using namespace std;
# define G 3
# define MAXN 262145
# define mod 998244353
# define inv 499122177
typedef long long int  ll;

ll A[MAXN],B[MAXN],rev[MAXN],tp[MAXN],tq[MAXN],ta[MAXN],tb[MAXN];


void init(int k)
{
    int len=(1<<k);

    for(int i=0;i<len;i++)
    {
        rev[i]=0;
    }
    for(int i=0;i<len;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
    }
    return ;

}

ll qp(ll base,ll pow)
{
    ll ans=1;

    while(pow)
    {
        if(pow&1)
        {
            ans=ans*base%mod;
        }

        pow>>=1;

        base=base*base%mod;

    }
    return ans;

}

void NTT(ll *a,int n,int flag)
{

    for(int i=0;i<n;i++)
    {
        if(i<rev[i])
        {
            swap(a[i],a[rev[i]]);

        }
    }

    for(int h=1;h<n;h<<=1)
    {
        ll gn=qp(G,(mod-1)/(h<<1));

        if(flag==-1)
        {
            gn=qp(gn,mod-2);

        }
        for(int j=0;j<n;j+=2*h)
        {

            ll g=1;

            for(int k=j;k<j+h;k++)
            {
                ll x=a[k];
                ll y=a[k+h]*g%mod;

                a[k]=(x+y)%mod;

                a[k+h]=((x-y)%mod+mod)%mod;

                g=gn*g%mod;

            }
        }
    }

    if(flag==-1)
    {
        ll invn=qp(n,mod-2);

        for(int i=0;i<n;i++)
        {

            a[i]=a[i]*invn%mod;

        }
    }
    return ;

}
void mul(ll *a,ll*b,ll*c,int n,int m)
{

    int k=1,s=2;

    while((1<<k)<n+m-1)
    {
        k++;
        s<<=1;

    }
    init(k);


    for(int i=0;i<n;i++)
    {
        tp[i]=a[i];
    }
    for(int i=n;i<s;i++)
    {
        tp[i]=0;
    }
    NTT(tp,s,1);

    for(int i=0;i<m;i++)
    {
        tq[i]=b[i];
    }

    for(int i=m;i<s;i++)
    {
        tq[i]=0;
    }

    NTT(tq,s,1);

    for(int i=0;i<s;i++)
    {
        c[i]=tp[i]*tq[i]%mod;

    }

    NTT(c,s,-1);

}

void getinv(ll *a,ll *b,int n)
{
    if(n==1)
    {
        b[0]=qp(a[0],mod-2);
        return ;

    }
    getinv(a,b,(n+1)>>1);

    int k=1,s=2;

    while((1<<k)<n+n-1)
    {
        k++;
        s<<=1;
    }
    init(k);
    for(int i=0;i<n;i++)
    {
        ta[i]=a[i];

    }
    for(int i=n;i<s;i++)
    {

        ta[i]=0;
    }
    NTT(ta,s,1);

    NTT(b,s,1);

    for(int i=0;i<s;i++)
    {
        b[i]=(2ll-ta[i]*b[i]%mod+mod)*b[i]%mod;

    }
    NTT(b,s,-1);

    for(int i=n;i<s;i++)
    {
        b[i]=0;
    }

}

void sqrt(ll *a,ll *b, int n)
{

    if(n==1)
    {
        b[0]=1;
        return ;
    }

    sqrt(a,b,(n+1)>>1);

    int k=1,s=2;

    while((1<<k)<n+n-1)
    {
        k++;

        s<<=1;

    }


    for(int i=0;i<s;i++)
    {
        tb[i]=0;
    }

    getinv(b,tb,n);

    mul(a,tb,tb,n,n);

    for(int i=0;i<s;i++)
    {
        b[i]=(b[i]+tb[i])*inv%mod;

    }

}
int main ()
{
    int n;
    cin>>n;

    for(int i=0;i<n;i++)
    {
        cin>>A[i];

    }

    sqrt(A,B,n);

    for(int i=0;i<n;i++)
    {
        cout<<B[i]<<" ";

    }
    return 0;

}