NTT (fast number theory transformation) polynomial inverse 1500 word analysis

First of all, we have

We are right. x^n Round up and open the root , namely

We set up

obviously

Subtracting two formulas

so

So the polynomial formed by subtraction is 0- All to the power 0, Otherwise, they themselves cannot be to be divisible by

Based on this finding

Square the subtraction

Multiply F(x) operation Again by

thus G(x) use NTT solve

# include<iostream>


using namespace std;
typedef long long int  ll;

const int mod=998244353,g=3,N=2000000;

int n;
ll a[N],b[N],c[N],rev[N];

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 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  ;

}

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(3ll,(mod-1)/(h*2));


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

        for(int j=0;j<n;j+=2*h)
        {
            ll gg=1;

            for(int k=j;k<j+h;k++)
            {
                ll x=a[k];

                ll y=gg*a[k+h]%mod;

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

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

                gg=gg*gn%mod;


            }
        }
    }

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

        for(int i=0;i<n;i++)
        {
            a[i]=a[i]*inv%mod;

        }
    }
}
void work(int pow,ll*a,ll *b)
{
    if(pow==1)
    {
        b[0]=qp(a[0],mod-2);

        return ;

    }

    work((pow+1)>>1,a,b);

    int k=1,s=2;

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

        s<<=1;

    }

    init(k);

    for(int i=0;i<pow;i++)    
    {
        c[i]=a[i];
    }
   
 /*
 The reason to use c save a, Not right a The direct operation is because each time we recurse 
 Must be of the original sequence a
*/

    NTT(c,s,1);

    NTT(b,s,1);

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

    NTT(b,s,-1);

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

    return ;


}

int main ()
{

    cin>>n;

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

    }

    work(n,a,b);

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

    }

    return 0;

}