Submission #72071187

---

Source Code Expand

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define pb emplace_back
#define i128 __int128
using namespace std;
const int mod = 998244353, _G = 3, N = (1 << 21), inv2 = (mod + 1) / 2;
#define add(a, b) (a + b >= mod ? a + b - mod : a + b)
#define dec(a, b) (a < b ? a - b + mod : a - b)
int qpow(int x, int y = mod - 2) {
	int res = 1;
	for(; y; x = (ll) x * x % mod, y >>= 1) if(y & 1) res = (ll) res * x % mod;
	return res;
}
int fac[N + 1], ifac[N + 1], inv[N + 1];
void init(int x) {
	fac[0] = ifac[0] = inv[1] = 1;
	L(i, 2, x) inv[i] = (ll) inv[mod % i] * (mod - mod / i) % mod;
	L(i, 1, x) fac[i] = (ll) fac[i - 1] * i % mod, ifac[i] = (ll) ifac[i - 1] * inv[i] % mod;
}
int C(int x, int y) {
	return y < 0 || x < y ? 0 : (ll) fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
inline int sgn(int x) {
	return (x & 1) ? mod - 1 : 1;
}
int rt[N], Lim;
void Pinit(int x) {
	for(Lim = 1; Lim <= x; Lim <<= 1) ;
	for(int i = 1; i < Lim; i <<= 1) {
		int sG = qpow (_G, (mod - 1) / (i << 1));
		rt[i] = 1;
		L(j, i + 1, i * 2 - 1) rt[j] = (ll) rt[j - 1] * sG % mod;
	}
}
struct poly {
	vector<int> a;
	int size() { return sz(a); }
	int & operator [] (int x) { return a[x]; }
	int v(int x) { return x < 0 || x >= sz(a) ? 0 : a[x]; }
	void clear() { vector<int> ().swap(a); }
	void rs(int x = 0) { a.resize(x); }
	poly (int n = 0) { rs(n); }
	poly (vector<int> o) { a = o; }
	poly (const poly &o) { a = o.a; }
	poly Rs(int x = 0) { vi res = a; res.resize(x); return res; }
	inline void dif() {
		int n = sz(a);
		for (int l = n >> 1; l >= 1; l >>= 1) 
			for(int j = 0; j < n; j += l << 1) 
				for(int k = 0, *w = rt + l; k < l; k++, w++) {
					int x = a[j + k], y = a[j + k + l];
					a[j + k] = add(x, y);
					a[j + k + l] = (ll) * w * dec(x, y) % mod;
				}
	}
	void dit () {
		int n = sz(a);
		for(int i = 2; i <= n; i <<= 1) 
			for(int j = 0, l = (i >> 1); j < n; j += i) 
				for(int k = 0, *w = rt + l; k < l; k++, w++) {
					int pa = a[j + k], pb = (ll) a[j + k + l] * *w % mod;
					a[j + k] = add(pa, pb), a[j + k + l] = dec(pa, pb);
				}
		reverse(a.begin() + 1, a.end());
		for(int i = 0, iv = qpow(n); i < n; i++) a[i] = (ll) a[i] * iv % mod;
	} 
	friend poly operator * (poly aa, poly bb) {
		if(!sz(aa) || !sz(bb)) return {};
		int lim, all = sz(aa) + sz(bb) - 1;
		for(lim = 1; lim < all; lim <<= 1);
		aa.rs(lim), bb.rs(lim), aa.dif(), bb.dif();
		L(i, 0, lim - 1) aa[i] = (ll) aa[i] * bb[i] % mod;
		aa.dit(), aa.a.resize(all);
		return aa;
	}
	poly Inv() {
		poly res, f, g;
		res.rs(1), res[0] = qpow(a[0]);
		for(int m = 1, pn; m < sz(a); m <<= 1) {
			pn = m << 1, f = res, g.rs(pn), f.rs(pn);
			for(int i = 0; i < pn; i++) g[i] = (*this).v(i);
			f.dif(), g.dif();
			for(int i = 0; i < pn; i++) g[i] = (ll) f[i] * g[i] % mod;
			g.dit();
			for(int i = 0; i < m; i++) g[i] = 0;
			g.dif();
			for(int i = 0; i < pn; i++) g[i] = (ll) f[i] * g[i] % mod;
			g.dit(), res.rs(pn);
			for(int i = m; i < min(pn, sz(a)); i++) res[i] = (mod - g[i]) % mod;
		} 
		return res.rs(sz(a)), res;
	}
	poly Shift (int x) {
		poly zm (sz(a) + x);
		L(i, max(-x, 0), sz(a) - 1) zm[i + x] = a[i];
		return zm; 
	}
	friend poly operator * (poly aa, int bb) {
		poly res(sz(aa));
		L(i, 0, sz(aa) - 1) res[i] = (ll) aa[i] * bb % mod;
		return res;
	}
	friend poly operator + (poly aa, poly bb) {
		vector<int> res(max(sz(aa), sz(bb)));
		L(i, 0, sz(res) - 1) res[i] = add(aa.v(i), bb.v(i));
		return poly(res);
	}
	friend poly operator - (poly aa, poly bb) {
		vector<int> res(max(sz(aa), sz(bb)));
		L(i, 0, sz(res) - 1) res[i] = dec(aa.v(i), bb.v(i));
		return poly(res);
	}
	poly & operator += (poly o) {
		rs(max(sz(a), sz(o)));
		L(i, 0, sz(a) - 1) (a[i] += o.v(i)) %= mod;
		return (*this);
	}
	poly & operator -= (poly o) {
		rs(max(sz(a), sz(o)));
		L(i, 0, sz(a) - 1) (a[i] += mod - o.v(i)) %= mod;
		return (*this);
	}
	poly & operator *= (poly o) {
		return (*this) = (*this) * o;
	}
	poly Integ() {
		if(!sz(a)) return poly();
		poly res(sz(a) + 1);
		L(i, 1, sz(a)) res[i] = (ll) a[i - 1] * inv[i] % mod;
		return res;
	}
	poly Deriv() {
		if(!sz(a)) return poly();
		poly res(sz(a) - 1); 
		L(i, 1, sz(a) - 1) res[i - 1] = (ll) a[i] * i % mod;
		return res;
	}
	poly Ln() {
		poly g = ((*this).Inv() * (*this).Deriv()).Integ();
		return g.rs(sz(a)), g;
	}
	poly Exp() {
		poly res(1), f; 
		res[0] = 1;
		for(int m = 1, pn; m < sz(a); m <<= 1) {
			pn = min(m << 1, sz(a)), f.rs(pn), res.rs(pn);
			for(int i = 0; i < pn; i++) f[i] = (*this).v(i);
			f -= res.Ln(), (f[0] += 1) %= mod, res *= f, res.rs(pn); 
		}
		return res.rs(sz(a)), res;
	}
	poly pow(int x, int rx = -1) { // x : the power % mod; rx : the power % (mod - 1)
		if(rx == -1) rx = x;
		int cnt = 0;
		while (a[cnt] == 0 && cnt < sz(a)) cnt += 1;
		
		poly res = (*this);
		L(i, cnt, sz(a) - 1) res[i - cnt] = res[i];
		L(i, sz(a) - cnt, sz(a) - 1) res[i] = 0;
		int c = res[0], w = qpow (res[0]);
		L(i, 0, sz(res) - 1) res[i] = (ll) res[i] * w % mod;
		res = res.Ln();
		L(i, 0, sz(res) - 1) res[i] = (ll) res[i] * x % mod;
		res = res.Exp();
		c = qpow (c, rx);
		L(i, 0, sz(res) - 1) res[i] = (ll) res[i] * c % mod;
		
		if((ll) cnt * x > sz(a)) L(i, 0, sz(a) - 1) res[i] = 0;
		else if(cnt) {
			R(i, sz(a) - cnt * x - 1, 0) res[i + cnt * x] = res[i];
			L(i, 0, cnt * x - 1) res[i] = 0; 
		}
		return res;
	}
	poly sqrt(int rt = 1) {
		poly res(1), f; 
		res[0] = rt;
		for(int m = 1, pn; m < sz(a); m <<= 1) {
			pn = min(m << 1, sz(a)), f.rs(pn);
			for(int i = 0; i < pn; i++) f[i] = (*this).v(i);
			f += res * res, f.rs(pn), res.rs(pn), res = f * res.Inv(), res.rs(pn);
			for(int i = 0; i < pn; i++) res[i] = (ll) res[i] * inv2 % mod;
		} 
		return res;
	}
	void Rev() {
		reverse(a.begin(), a.end());
	}
	friend pair < poly, poly > div (poly f, poly g) { /* f / g = first, f % g = second */
		f.rs(max(sz(f), sz(g))), f.Rev(), g.Rev();
		int n = sz(f), m = sz(g);
		poly A = g.Rs(n - m + 1).Inv(), t;
		A *= f.Rs(n - m + 1), A.rs(n - m + 1), A.Rev(), g.Rev(), f.Rev(), t = f - A * g, t.rs(m - 1);
		return make_pair(A, t);
	} 
} ;


namespace qwqwq{
using u32=unsigned;
using i64=long long;
using u64=unsigned long long;
using std::cin;
using std::cout;
constexpr u32 mod=998244353,_g=3;
constexpr auto mul(u32 x,u32 y)->u32{
    return u64(x)*y%mod;
}
constexpr auto dilt(u32 x,u32 M){
    return std::min(x,x+M);
}
constexpr auto shrk(u32 x,u32 M){
    return std::min(x,x-M);
}
constexpr auto qpw(u32 a,u32 b,u32 r=1){
    for(;b;b>>=1,a=mul(a,a)){
        if(b&1){
            r=mul(r,a);
        }
    }
    return r;
}
constexpr auto bcl(int x){
    return (x<2)?1:2<<std::__lg(x-1);
}
std::vector<u32> _w{1},iw{1},_w22{1};
auto init_w(int lm){
    _w.resize(lm),iw.resize(lm),_w22.resize(lm);
    for(auto i=1;i<lm;i<<=1){
        _w[i]=qpw(_g,((mod-1)>>2)/i);
        iw[i]=qpw(_g,mod-1-((mod-1)>>2)/i);
    }
    for(auto i=1;i<lm;++i){
        _w[i]=mul(_w[i&(i-1)],_w[i&-i]);
        iw[i]=mul(iw[i&(i-1)],iw[i&-i]);
    }
    for(auto i=1,i2=2;i<lm;i=i2,i2<<=1){
		auto _G=qpw(_g,(mod-1)/i2),r=mod-(mod-1)/i;
		for(auto j=i;j<i2;++j){
		    _w22[j]=r,r=mul(r,_G);
		}
	}
}
inline auto chk_w(int lm){
    if((lm>>=1)>int(_w.size())){
        init_w(lm);
    }
}
inline auto rot_R(u32*f,int L,u32 r){
    for(auto i=0;i<L;++i){
        auto x=f[i],y=mul(f[i+L],r);
        f[i]=shrk(x+y,mod),f[i+L]=dilt(x-y,mod);
    }
}
inline auto rot_L(u32*f,int L,u32 r){
    for(auto i=0;i<L;++i){
        auto x=f[i],y=f[i+L];
        f[i]=shrk(x+y,mod),f[i+L]=mul(x-y+mod,r);
    }
}
inline auto rrot_R(u32*f,int L,int lm){
    for(auto j=0,k=0;j<lm;j+=L*2,++k){
        rot_R(f+j,L,_w[k]);
    }
}
inline auto rrot_L(u32*f,int L,int lm){
    for(auto j=0,k=0;j<lm;j+=L*2,++k){
        rot_L(f+j,L,iw[k]);
    }
}
int fft_len=0;
auto dif(u32*f,int lm){
    fft_len+=lm;
    chk_w(lm);
    for(auto L=lm>>1;L;L>>=1){
        rrot_R(f,L,lm);
    }
}
auto fft_2D(u32*f,int n,int m){
    auto lm=n*m;
    fft_len+=lm;
    chk_w(lm);
    for(auto j=0;j<lm;j+=m){
        for(auto L=m>>1;L;L>>=1){
            rrot_R(f+j,L,m);
        }
    }
    for(auto L=lm>>1;L>=m;L>>=1){
        rrot_R(f,L,lm);
    }
}
auto print_2D(u32*f,int n,int m,int x=1){
    int fx=qpw(x,mod-2);
    cout<<"n:"<<n<<" m:"<<m<<"\n";
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            cout<<mul(fx,f[i*m+j])<<" \n"[j+1==m];
        }
    }
}
auto dit(u32*f,int lm){
    fft_len+=lm;
    for(auto L=1;L<lm;L<<=1){
        rrot_L(f,L,lm);
    }
}
template<bool fx=true>auto ifft_2D(u32*f,int n,int m){
    auto lm=n*m;
    fft_len+=lm;
    for(auto j=0;j<lm;j+=m){
        for(auto L=1;L<m;L<<=1){
            rrot_L(f+j,L,m);
        }
    }
    for(auto L=m;L<lm;L<<=1){
        rrot_L(f,L,lm);
    }
    if constexpr(fx){
        const u32 iv=mod-(mod-1)/lm;
        for(auto i=0;i<lm;++i){
            f[i]=mul(f[i],iv);
        }
    }
}
inline auto dot(u32*f,const u32*g,int lm){
    for(auto i=0;i<lm;++i){
        f[i]=mul(f[i],g[i]);
    }
}
inline auto rdot(const u32*f,const u32*g,u32*h,int lm){
    for(auto i=0;i<lm;++i){
        h[i]=mul(f[i],g[i]);
    }
}
std::vector<u32> fac{1},ifac{1},iv{0};
auto init_fac(int n){
    fac.resize(n),ifac.resize(n),iv.resize(n);
	for(auto i=1;i<n;++i){fac[i]=mul(fac[i-1],i);}
	ifac[n-1]=qpw(fac[n-1],mod-2);
	for(auto i=n-1;i>0;--i){ifac[i-1]=mul(ifac[i],i),iv[i]=mul(ifac[i],fac[i-1]);}
}
inline auto chk_fac(int n){
    if(n>int(fac.size())){
        init_fac(std::max(n,int(fac.size())*2));
    }
}
std::vector<u32> Ax,Bx,Cx,Dx;
inline auto toBuf(std::vector<u32>&f,int lm){
    f.resize(lm);
    return f.data();
}
constexpr auto iv4=qpw(4,mod-2);
auto Inv(const u32*f,u32*g,int n){
	g[0]=qpw(f[0],mod-2);
	auto lm=bcl(n);
    auto ax=toBuf(Ax,lm),bx=toBuf(Bx,lm);
    auto fx=mod-iv4;
	for(auto t=2,m=1;t<=lm;m=t,t<<=1,fx=mul(fx,iv4)){
		auto xl=std::min(t,n);
		std::fill(std::copy_n(f,xl,ax),ax+t,0),std::fill(std::copy_n(g,m,bx),bx+t,0);
		dif(ax,t),dif(bx,t),dot(ax,bx,t),dit(ax,t),std::fill_n(ax,m,0),dif(ax,t),dot(ax,bx,t),dit(ax,t);
        for(auto i=m;i<xl;++i){g[i]=mul(ax[i],fx);}
	}
}
auto Quo(const u32*f,const u32*g,u32*h,int n){
	if(n==1){*h=qpw(*g,mod-2,*f);return;}
	auto lm=bcl(n),hl=lm>>1;
    const u32 iv=mod-(mod-1)/lm;
    auto ax=toBuf(Ax,lm),bx=toBuf(Bx,lm),cx=toBuf(Cx,lm);
	Inv(g,cx,hl),std::fill_n(cx+hl,hl,0),dif(cx,lm),std::fill(std::copy_n(f,hl,ax),ax+lm,0),dif(ax,lm),dot(ax,cx,lm),dit(ax,lm);
	for(auto i=0;i<hl;++i){h[i]=ax[i]=mul(ax[i],iv);}
	std::fill_n(ax+hl,hl,0),dif(ax,lm),std::fill(std::copy_n(g,n,bx),bx+lm,0),dif(bx,lm),dot(ax,bx,lm),dit(ax,lm),std::fill_n(ax,hl,0);
	for(auto i=hl;i<n;++i){ax[i]=(u64(ax[i])*iv+(mod-f[i]))%mod;}
	dif(ax,lm),dot(ax,cx,lm),dit(ax,lm);
    const u32 _iv=mod-iv;
	for(auto i=hl;i<n;++i){h[i]=mul(ax[i],_iv);}
}
auto Ln(const u32*f,u32*g,int n){
    auto dx=toBuf(Dx,n);
	for(auto i=0;i<n;++i){
        dx[i]=mul(f[i],i);
    }
	Quo(dx,f,g,n),dot(g,iv.data(),n);
}
auto Exp(const u32*f,u32*g,int n){
	auto lm=bcl(n);
    auto ax=toBuf(Ax,lm),bx=toBuf(Bx,lm),cx=toBuf(Cx,lm),dx=toBuf(Dx,lm);
    g[0]=dx[0]=ax[0]=ax[1]=1;
    auto fx=mod-iv4;
	for(auto t2=4,t=2,m=1;t<=lm;m=t,t=t2,t2<<=1,fx=mul(fx,iv4)){
		auto xl=std::min(t,n);
		for(auto i=0;i<m;++i){cx[i]=mul(f[i],i);}
		dif(cx,m),dot(cx,ax,m),dit(cx,m);
        const u32 IV=(mod-1)/m;
		for(auto i=0;i<m;++i){cx[m+i]=(u64(g[i])*i+u64(cx[i])*IV)%mod,cx[i]=0;}
		dif(cx,t),std::fill(std::copy(dx,dx+m,bx),bx+t,0),dif(bx,t),dot(cx,bx,t),dit(cx,t);
		const u32 Iv=(mod-1)/t;
        for(int i=m;i<t;++i){cx[i]=(mul(cx[i],Iv)*u64(iv[i])+(f[i]))%mod,cx[i-m]=0;}
		dif(cx,t),dot(cx,ax,t),dit(cx,t);
        const u32 iv=mod-Iv;
		for(int i=m;i<xl;++i){g[i]=mul(cx[i],iv);}
		if(t!=lm){
			std::fill(std::copy_n(g,t,ax),ax+t2,0),dif(ax,t2),rdot(ax,bx,cx,t),dit(cx,t);
			for(auto i=m;i<t;++i){cx[i]=mul(cx[i],fx),cx[i-m]=0;}
			dif(cx,t),dot(cx,bx,t),dit(cx,t),std::copy(cx+m,cx+t,dx+m);
		}
	}
}
auto __PowerXY(std::vector<u32> g,int n){
    std::vector<u32> dftP(4*n,1),dftQ(4*n);
    for(auto i=0;i<n;++i){dftQ[i]=dilt(-g[i],mod);}
    chk_w(n*2);
    for(auto L=n;L;L>>=1){rrot_R(dftQ.data(),L,n*2);}
    std::fill(dftQ.begin()+n*2,dftQ.end(),1);
    rot_R(dftQ.data(),n*2,1);
    auto k=1,t=n;
    u32 One=1;
    for(;;t>>=1,k<<=1){
        for(auto i=0;i<2*k;++i){
            for(auto j=0;j<2*t;j+=2){
                auto p=i*(2*t)+j,q=i*t+j/2;
                auto x=dftQ[p],y=dftQ[p+1];
                dftP[q]=mul(mul(dftP[p],y)-mul(dftP[p+1],x)+mod,iw[j/2]);
                dftQ[q]=mul(x,y);
            }
        }
        One=mul(One,One);
        if(t==2){
            ifft_2D<false>(dftP.data(),2*k,t);
            const u32 fx=qpw(mul(One,2*n),mod-2);
            for(auto i=0;i<n;++i){
                dftP[i]=mul(fx,dftP[i<<1]);
            }
            dftP.resize(n);
            break;
        }
        else{
            fft_len += 8*n;
            {
            for(auto i=0;i<2*k;++i){
                auto dft=dftP.data()+i*t;
                for(auto L=1;L<t;L<<=1){
                    rrot_L(dft,L,t);
                }
                std::fill(dft+t/2,dft+t,0);
                for(auto L=t>>1;L;L>>=1){
                    rrot_R(dft,L,t);
                }
            }
            auto g=dftP.data()+2*n;
            std::copy(dftP.cbegin(),dftP.cbegin()+2*n,g);
            for(auto L=t;L<n*2;L<<=1){
                rrot_L(g,L,n*2);
            }
            for(int j=0,k=0,diff=(n*2)/t;j<n*2;j+=t,++k){
                for(int i=0;i<t;++i){
                    g[j+i]=mul(g[j+i],_w22[diff+k]);
                }
            }
            for(auto L=n;L>=t;L>>=1){
                rrot_R(g,L,n*2);
            }

            }
            {
            for(auto i=0;i<2*k;++i){
                auto dft=dftQ.data()+i*t;
                for(auto L=1;L<t;L<<=1){
                    rrot_L(dft,L,t);
                }
                std::fill(dft+t/2,dft+t,0);
                for(auto L=t>>1;L;L>>=1){
                    rrot_R(dft,L,t);
                }
            }
            auto g=dftQ.data()+2*n;
            std::copy(dftQ.cbegin(),dftQ.cbegin()+2*n,g);
            
            for(auto L=t;L<n*2;L<<=1){
                rrot_L(g,L,n*2);
            }
            for(int j=0,k=0,diff=(n*2)/t;j<n*2;j+=t,++k){
                for(int i=0;i<t;++i){
                    g[j+i]=mul(g[j+i],_w22[diff+k]);
                }
            }
            One=mul(One,t);
            u32 Two=shrk(One+One,mod);
            for(int i=0;i<t;++i){
                g[i]=dilt(g[i]-Two,mod);
            }
            for(auto L=n;L>=t;L>>=1){
                rrot_R(g,L,n*2);
            }

            }
        }
    }
    return dftP;
}
auto CompInv(std::vector<u32> g,int n){
    int lm=bcl(n);

    g.resize(lm);
    int v=qpw(g[1],mod-2);
    for(auto&x:g){x=mul(x,v);}
    auto G=__PowerXY(g,lm);
    chk_fac(lm);
    for(int i=0,fx=1;i<lm;++i){
        g[i]=mul(mul(fx,iv[lm-i-1]),mul(G[i],lm-1));
        fx=mul(fx,v);
    }
    Ln(g.data(),G.data(),lm);
    for(auto&x:G){x=mul(x,mod-iv[lm-1]);}
    Exp(G.data(),g.data()+1,lm-1),g[0]=0;
    for(int i=1;i<lm;++i){g[i]=mul(g[i],v);}

    g.resize(n);
    return g;
}
auto solve(){
    int n;
    cin>>n;
    std::vector<u32> f(n);
    for(auto&x:f){
        cin>>x;
    }
    for(auto x:CompInv(f,n)){
        cout<<x<<" ";
    }
    std::cerr<<"\nfft_len:"<<fft_len<<"\n";
}
}

namespace qwq{
	using u32=unsigned;
using i64=long long;
using u64=unsigned long long;
using std::cin;
using std::cout;
constexpr u32 mod=998244353,_g=3;
constexpr auto mul(u32 x,u32 y)->u32{
    return u64(x)*y%mod;
}
constexpr auto dilt(u32 x,u32 M){
    return std::min(x,x+M);
}
constexpr auto shrk(u32 x,u32 M){
    return std::min(x,x-M);
}
constexpr auto qpw(u32 a,u32 b,u32 r=1){
    for(;b;b>>=1,a=mul(a,a)){
        if(b&1){
            r=mul(r,a);
        }
    }
    return r;
}
constexpr auto bcl(int x){
    return (x<2)?1:2<<std::__lg(x-1);
}
std::vector<u32> _w{1},iw{1},_w22{1},iw22{1};
auto init_w(int lm){
    _w.resize(lm),iw.resize(lm),_w22.resize(lm),iw22.resize(lm);
    for(auto i=1;i<lm;i<<=1){
        _w[i]=qpw(_g,((mod-1)>>2)/i);
        iw[i]=qpw(_g,mod-1-((mod-1)>>2)/i);
    }
    for(auto i=1;i<lm;++i){
        _w[i]=mul(_w[i&(i-1)],_w[i&-i]);
        iw[i]=mul(iw[i&(i-1)],iw[i&-i]);
    }
    for(auto i=1,i2=2;i<lm;i=i2,i2<<=1){
		auto _G=qpw(_g,(mod-1)/i2),_r=mod-(mod-1)/i;
        auto iG=qpw(_G,mod-2),ir=mod-(mod-1)/i;
		for(auto j=i;j<i2;++j){
		    _w22[j]=_r,_r=mul(_r,_G);
            iw22[j]=ir,ir=mul(ir,iG);
		}
	}
}
inline auto chk_w(int lm){
    if((lm>>=1)>int(_w.size())){
        init_w(lm);
    }
}
inline auto rot_R(u32*f,int L,u32 r){
    for(auto i=0;i<L;++i){
        auto x=f[i],y=mul(f[i+L],r);
        f[i]=shrk(x+y,mod),f[i+L]=dilt(x-y,mod);
    }
}
inline auto rot_L(u32*f,int L,u32 r){
    for(auto i=0;i<L;++i){
        auto x=f[i],y=f[i+L];
        f[i]=shrk(x+y,mod),f[i+L]=mul(x-y+mod,r);
    }
}
inline auto rrot_R(u32*f,int L,int lm){
    for(auto j=0,k=0;j<lm;j+=L*2,++k){
        rot_R(f+j,L,_w[k]);
    }
}
inline auto rrot_L(u32*f,int L,int lm){
    for(auto j=0,k=0;j<lm;j+=L*2,++k){
        rot_L(f+j,L,iw[k]);
    }
}
int fft_len=0;
auto dif(u32*f,int lm){
    fft_len+=lm;
    chk_w(lm);
    for(auto L=lm>>1;L;L>>=1){
        rrot_R(f,L,lm);
    }
}
auto fft_2D(u32*f,int n,int m){
    auto lm=n*m;
    fft_len+=lm;
    chk_w(lm);
    for(auto j=0;j<lm;j+=m){
        for(auto L=m>>1;L;L>>=1){
            rrot_R(f+j,L,m);
        }
    }
    for(auto L=lm>>1;L>=m;L>>=1){
        rrot_R(f,L,lm);
    }
}
auto dit(u32*f,int lm){
    fft_len+=lm;
    for(auto L=1;L<lm;L<<=1){
        rrot_L(f,L,lm);
    }
}
template<bool fx=true>auto ifft_2D(u32*f,int n,int m){
    auto lm=n*m;
    fft_len+=lm;
    for(auto j=0;j<lm;j+=m){
        for(auto L=1;L<m;L<<=1){
            rrot_L(f+j,L,m);
        }
    }
    for(auto L=m;L<lm;L<<=1){
        rrot_L(f,L,lm);
    }
    if constexpr(fx){
        const u32 iv=mod-(mod-1)/lm;
        for(auto i=0;i<lm;++i){
            f[i]=mul(f[i],iv);
        }
    }
}
inline auto dot(u32*f,const u32*g,int lm){
    for(auto i=0;i<lm;++i){
        f[i]=mul(f[i],g[i]);
    }
}
inline auto rdot(const u32*f,const u32*g,u32*h,int lm){
    for(auto i=0;i<lm;++i){
        h[i]=mul(f[i],g[i]);
    }
}
std::vector<u32> fac{1},ifac{1},iv{0};
auto init_fac(int n){
    fac.resize(n),ifac.resize(n),iv.resize(n);
	for(auto i=1;i<n;++i){fac[i]=mul(fac[i-1],i);}
	ifac[n-1]=qpw(fac[n-1],mod-2);
	for(auto i=n-1;i>0;--i){ifac[i-1]=mul(ifac[i],i),iv[i]=mul(ifac[i],fac[i-1]);}
}
inline auto chk_fac(int n){
    if(n>int(fac.size())){
        init_fac(std::max(n,int(fac.size())*2));
    }
}
auto __PowerYX(u32*P,u32*tQ,int n,int m,u32&OneP,u32&OneQ){
    if(m==1){
        dif(P,n);
        for(int i=n-1;i>=0;--i){
            u32 x=P[i];
            P[i*2]=x,P[i*2+1]=x;
        }
        return;
    }
    u32*Q=new u32[4*n*m];
    if(n==1){
        for(int i=0;i<m;++i){Q[i]=dilt(-tQ[i],mod);}
        std::fill(Q+m,Q+m*2,0),dif(Q,m*2);
        std::fill(Q+m*2,Q+m*4,1),rot_R(Q,m*2,1);
    }
    else{
        fft_len += 4*n*m;
        for(int i=0;i<2*n*m;++i){
            Q[i]=mul(tQ[i*2],tQ[i*2+1]);
        }
        OneQ=mul(OneQ,OneQ);
        for(auto i=0;i<n;++i){
            auto dft=Q+i*m*2;
            for(auto L=1;L<=m;L<<=1){
                rrot_L(dft,L,m*2);
            }
            std::fill_n(dft+m,m,0);
            for(auto L=m;L;L>>=1){
                rrot_R(dft,L,m*2);
            }
        }
        auto g=Q+2*n*m;
        std::copy(Q,g,g);
        for(auto L=m*2;L<=n*m;L<<=1){
            rrot_L(g,L,2*n*m);
        }
        for(int j=0,k=0,diff=n;j<n*m*2;j+=m*2,++k){
            for(int i=0;i<m*2;++i){
                g[j+i]=mul(g[j+i],_w22[diff+k]);
            }
        }
        OneQ=mul(OneQ,m*2);
        u32 Two=shrk(OneQ+OneQ,mod);
        for(int i=0;i<m*2;++i){
            g[i]=dilt(g[i]-Two,mod);
        }
        for(auto L=n*m;L>m;L>>=1){
            rrot_R(g,L,2*n*m);
        }
    }
    const u32 oo=OneQ;
    __PowerYX(P,Q,n*2,m/2,OneP,OneQ);
    for(int i=0;i<2*n*m;++i){
        auto x=Q[i*2],y=Q[i*2+1];
        Q[i*2]=mul(P[i],y);
        Q[i*2+1]=mul(P[i],x);
    }
    OneP=mul(OneP,oo);
    if(n==1){
        ifft_2D<false>(Q,2*n,2*m);
        u32 fx=qpw(mul(4*n*m,OneP),mod-2);
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                P[i*m+j]=mul(Q[(i+n)*(2*m)+j],fx);
            }
        }
    }
    else{
        fft_len += 4*n*m;
        auto g=Q+2*n*m;
        for(auto L=2*m;L<=n*m;L<<=1){
            rrot_L(g,L,2*n*m);
        }
        for(int j=0,k=0,diff=n;j<n*m*2;j+=m*2,++k){
            for(int i=0;i<m*2;++i){
                g[j+i]=mul(g[j+i],iw22[diff+k]);
            }
        }
        for(auto L=n*m;L>m;L>>=1){
            rrot_R(g,L,2*n*m);
        }
        OneP=mul(OneP,2);
        for(auto i=0;i<2*n*m;++i){
            P[i]=dilt(Q[i]-g[i],mod);
        }
        for(auto i=0;i<n;++i){
            auto dft=P+i*m*2;
            for(auto L=1;L<=m;L<<=1){
                rrot_L(dft,L,m*2);
            }
            std::fill_n(dft+m,m,0);
            for(auto L=m;L;L>>=1){
                rrot_R(dft,L,m*2);
            }
        }
        OneP=mul(OneP,m*2);
    }
    delete []Q;
}
auto Comp(std::vector<u32> f,std::vector<u32> g,int n){
    auto lm=bcl(std::max<int>(f.size(),n));
    f.resize(lm),g.resize(lm);

    if(g[0]){
        f.resize(lm*2);
        std::vector<u32> h(lm*2);
        h[0]=mod-mod/(lm*2),chk_fac(lm);
        auto c=g[0],cn=mul(c,h[0]);
        for(auto i=1;i<lm;++i){
            h[lm*2-i]=mul(cn,ifac[i]),cn=mul(cn,c);
            f[i]=mul(f[i],fac[i]);
        }
        dif(f.data(),lm*2),dif(h.data(),lm*2);
        dot(f.data(),h.data(),lm*2);
        dit(f.data(),lm*2),dot(f.data(),ifac.data(),lm);
        f.resize(lm),g[0]=0;
    }//taylor shift.

    if(lm!=1){
        f.resize(lm*2);
        u32 op=1,oq=1;
        __PowerYX(f.data(),g.data(),1,lm,op,oq);
    }

    f.resize(n);
    return f;
}
auto solve(){
    int n;
    cin>>n;
    std::vector<u32> F(n),G(n);
    for(auto&x:F){cin>>x;}
    for(auto&x:G){cin>>x;}
    for(auto x:Comp(F,G,n)){
        cout<<x<<" ";
    }
    std::cerr<<"\nfft_len : "<<fft_len<<"\n";
}
}


const int L = 1e8;
int n, m;

int A[N];

pair<poly,poly>dv(int l, int r) {
    if(l == r) {
        poly f = vi{1};
        poly g = vi{1, mod - A[l]};
        return make_pair(f, g);
    }
    int mid = (l + r) >> 1;
    auto ls = dv(l, mid);
    auto rs = dv(mid + 1, r);
    return make_pair(ls.first * rs.second + ls.second * rs.first, ls.second * rs.second);
}
int ps[N];
void compute_e() {
    auto mp = dv(1, m);
    auto ans = mp.first * (mp.second.Rs(n + 1)).Inv();
    L(i, 0, n) {
        ps[i] = ans[i];
    }
}
int main () {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    cin >> n >> m;
    L(i, 1, m) cin >> A[i];
    init(n * 4 + 10);
    Pinit(n * 4 + 10);
    compute_e();
    poly tot(n + 1);
    poly f(n + 1);
    //cout << ps[1] << ' ' << ps[2] << endl;
    L(i, 0, n) {
        tot[i] = (ll) qpow(L, i) * ifac[i] % mod;
    }
    L(i, 0, n) {
        f[i] = (tot[i + 1] + mod - (ll) ps[i + 1] * qpow(m) % mod * ifac[i + 1] % mod) % mod;
    }
    poly sam(n + 1);
    L(i, 1, n) {
        sam[i] = (ll)qpow(i, i - 1) % mod * ifac[i] % mod * qpow(L, i - 1) % mod;
    }
    vector<qwq::u32>f1(n + 1), f2(n + 1);
	L(i, 0, n) f1[i] = f[i], f2[i] = sam[i];
    //cout << f[0] << ' ' << f[1] << ' ' << f[2] << ' ' << f[3] << endl;
    auto ans = qwq::Comp(f1, f2, n + 1);
    poly res(n + 1);
    //cout << "ans0 = " << ans[0] << endl;
    L(i, 1, n) res[i] = ans[i - 1];
    res = (vi{1} - res).Inv();
    L(i, 1, n) cout << (ll) res[i] * fac[i] % mod * qpow(qpow((ll)i * L % mod), i) % mod << "\n";
    return 0;
} 

Submission Info

Compile Error

./Main.cpp: In member function 'poly poly::Inv()':
./Main.cpp:86:42: warning: implicitly-declared 'constexpr poly& poly::operator=(const poly&)' is deprecated [-Wdeprecated-copy]
   86 |                         pn = m << 1, f = res, g.rs(pn), f.rs(pn);
      |                                          ^~~
./Main.cpp:50:9: note: because 'poly' has user-provided 'poly::poly(const poly&)'
   50 |         poly (const poly &o) { a = o.a; }
      |         ^~~~
./Main.cpp: In member function 'poly& poly::operator*=(poly)':
./Main.cpp:130:44: warning: implicitly-declared 'constexpr poly& poly::operator=(const poly&)' is deprecated [-Wdeprecated-copy]
  130 |                 return (*this) = (*this) * o;
      |                                            ^
./Main.cpp:50:9: note: because 'poly' has user-provided 'poly::poly(const poly&)'
   50 |         poly (const poly &o) { a = o.a; }
      |         ^~~~
./Main.cpp: In member function 'poly poly::pow(int, int)':
./Main.cpp:168:30: warning: implicitly-declared 'constexpr poly& poly::operator=(const poly&)' is deprecated [-Wdeprecated-copy]
  168 |                 res = res.Ln();
      |                              ^
./Main.cpp:50:9: note: because 'poly' has user-provided 'poly::poly(const poly&)'
   50 |         poly (const poly &o) { a = o.a; }
      |         ^~~~
./Main.cpp:170:31: warning: implicitly-declared 'constexpr poly& poly::operator=(const poly&)' is deprecated [-Wdeprecated-copy]
  170 |                 res = res.Exp();
      |                               ^
./Main.cpp:50:9: note: because 'poly' has user-provided 'poly::poly(const poly&)'
   50 |         poly (const poly &o) { a = o.a; }
      |         ^~~~
./Main.cpp: In member function 'poly poly::sqrt(int)':
./Main.cpp:187:81: warning: implicitly-declared 'constexpr poly& poly::operator=(const poly&)' is deprecated [-Wdeprecated-copy]
  187 |                         f += res * res, f.rs(pn), res.rs(pn), res = f * res.Inv(), res.rs(pn);
      |                                                                                 ^
./Main.cpp:50:9: note: because 'poly' has user-provided 'poly::poly(const poly&)'
   50 |         poly (const poly &o) { a = o.a; }
      |         ^~~~
./Main.cpp: In function 'std::pair<poly, poly> div(poly, poly)':
./Main.cpp:199:95: warning: implicitly-declared 'constexpr poly& poly::operator=(const poly&)' is deprecated [-Wdeprecated-copy]
  199 |                 A *= f.Rs(n - m + 1), A.rs(n - m + 1), A.Rev(), g.Rev(), f.Rev(), t = f - A * g, t.rs(m - 1);
      |                                                                                               ^
./Main.cpp:50:9: note: because 'poly' has user-provided 'poly::poly(const poly&)'
   50 |         poly (const poly &o) { a = o.a; }
      |         ^~~~
./Main.cpp: In function 'int main()':
./Main.cpp:875:29: warning: implicitly-declared 'constexpr poly& poly::operator=(const poly&)' is deprecated [-Wdeprecated-copy]
  875 |     res = (vi{1} - res).Inv();
      |                             ^
./Main.cpp:50:9: note: because 'poly' has user-provided 'poly::poly(const poly&)'
   50 |         poly (const poly &o) { a = o.a; }
      |         ^~~~

Judge Result