多项式运算封装

动态更新。

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define il inline
#define rg register

using namespace std;

inline int read()
{
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
void write(int x)
{
    if(x<0) x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int N=4e6+10;
int n,m;
il int qpow(int a,int b,const int mod)
{
    rg int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
namespace poly
{
    const int g=114514,mod=998244353;
    const int inv_g=qpow(g,mod-2,mod);
    #define vint vector<int>
    #define sz(a) ((int)a.size())
    vint split(vint a,int n)
    {
        a.resize(n,0);
        return a;
    }
    void print(vint f)
    {
        for(int i:f)
        {
            cout<<i<<" ";
        }
        cout<<endl;
    }
    void NTT(vint& f)
    {
        int n=sz(f);
        if(n==1) return;
        vint f1(n/2,0),f2(n/2,0);
        for(rg int i=0;i<n/2;++i)
        {
            f1[i]=f[i<<1],f2[i]=f[i<<1|1];
        }
        NTT(f1),NTT(f2);
        int g_i=qpow(g,(mod-1)/n,mod),gk=1;
        for(int i=0;i<sz(f2);++i)
        {
            (f[i]=(f1[i]+f2[i]*gk)%mod)%=mod;
            (f[i+n/2]=(mod+(f1[i]-f2[i]*gk)%mod)%mod)%=mod;
            gk=g_i*gk%mod;
        }
    }
    void INTT(vint& f)
    {
        NTT(f);
        auto it=f.begin();
        ++it;
        reverse(it,f.end());
    }
    vint operator *(vint a,vint b)
    {
        int n=a.size(),m=b.size();
        vint res(n+m-1,0);
        int len=1;
        while(len<=n+m-2) len<<=1;
        int inv_len=qpow(len,mod-2,mod); 
        a.resize(len,0),b.resize(len,0);
        NTT(a),NTT(b);
        
        for(int i=0;i<len;++i)
        {
            a[i]=a[i]*b[i]%mod;
        }
        
        INTT(a);
        for(int i=0;i<=n+m-2;++i)
        {
            res[i]=a[i]*inv_len%mod;
        }
        return res;
    }
    vint operator +(vint a,vint b)
    {
        int len=max(sz(a),sz(b));
        vint res(len,0);
        a.resize(len,0),b.resize(len,0);
        for(rg int i=0;i<len;++i)
        {
            res[i]=(a[i]+b[i])%mod;
        }
        return res;
    }
    vint operator -(vint a,vint b)
    {
        int len=max(sz(a),sz(b));
        vint res(len,0);
        a.resize(len,0);
        b.resize(len,0);
        for(rg int i=0;i<len;++i)
        {
            res[i]=((a[i]-b[i])%mod+mod)%mod;
        }
        return res;
    }
    vint operator *(const vint a,int b)
    {
        vint res(a.size(),0);
        for(rg int i=0;i<sz(a);++i)
        {
            res[i]=a[i]*b%mod;
        }
        return res;
    }
    vint inv(vint a)
    {
        int n=sz(a);
        if(n==1) return vint{qpow(a[0],mod-2,mod)};
        vint b=inv(split(a,(n+1)>>1));
        vint p1=b*2,p2=a*b*b;
        return split(p1-p2,n);
    }
}
using namespace poly;

vint a,b;
signed main()
{
    n=read();
    a.resize(n,0);
    for(int i=0;i<n;++i) a[i]=read();
    b=inv(a);
    print(b);
    return 0;
}