提出 #70710592

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
#ifdef LOCAL
typedef long long LLL;
typedef unsigned long long uLLL;
#else
typedef __int128 LLL;
typedef unsigned __int128 uLLL;
#endif
typedef vector<int> poly;
typedef vector<int> Vec;
typedef vector<Vec> Mat;
typedef tuple<poly,poly,poly,poly> Mat2;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int Mod=998244353,G=3;
const LL Mod2=(LL)Mod*Mod;
vector<uLL>Grt,iGrt;
poly frc({1,1}),inv({0,1}),ivf({1,1});
inline int qpow(int x,int y,int z=1){
	for(;y;(y>>=1)&&(x=(LL)x*x%Mod))if(y&1)z=(LL)z*x%Mod;return z;
}
inline void Init(const int&n){
	for(int i=frc.size();i<=n;++i)
		frc.emplace_back((LL)frc.back()*i%Mod),
		inv.emplace_back(Mod-Mod/i*(LL)inv[Mod%i]%Mod),
		ivf.emplace_back((LL)ivf.back()*inv.back()%Mod);
}
inline int Binom(const int&n,const int&m){
	if(n<m||m<0)return 0;
	return Init(n),(LL)frc[n]*ivf[m]%Mod*ivf[n-m]%Mod;
}
inline uLL trans(const uLL&x){
    constexpr uLL A=-(uLL)Mod/Mod+1;
    constexpr uLL Q=(((uLLL)(-(uLL)Mod%Mod)<<64)+Mod-1)/Mod;
    return x*A+(uLL)((uLLL)x*Q>>64)+1;
}
inline uLL mul(const uLL&x,const uLL&y){
    return x*y*(uLLL)Mod>>64;
}
inline int add(int x,const int&y){
    return ((x+=y)-Mod)>=0?x-Mod:x;
}
inline int sub(int x,const int&y){
    return (x-=y)<0?x+Mod:x;
}
inline int div2(const int&x){
    return x&1?(x+Mod)>>1:x>>1;
}
inline bool Empty(poly&P){
	for(;!P.empty()&&!P.back();P.pop_back());
	return P.empty();
}
inline poly Add(poly P,poly Q){
    if(P.size()<Q.size())P.swap(Q);
    for(int i=Q.size();i--;)P[i]=add(P[i],Q[i]);
    return P;
}
inline poly Add_Empty(poly P,poly Q){
    if(P.size()<Q.size())P.swap(Q);
    for(int i=Q.size();i--;)P[i]=add(P[i],Q[i]);
    return Empty(P),P;
}
inline poly Sub(poly P,poly Q){
    if(P.size()<Q.size())P.resize(Q.size());
    for(int i=Q.size();i--;)P[i]=sub(P[i],Q[i]);
    return P;
}
inline poly Sub_Empty(poly P,poly Q){
    if(P.size()<Q.size())P.resize(Q.size());
    for(int i=Q.size();i--;)P[i]=sub(P[i],Q[i]);
    return Empty(P),P;
}
inline poly Mulx(poly P,int x){
    const uLL v=trans(x);
	for(int&i:P)i=mul(i,v);
	return P;
}
inline poly Neg(poly P){
	for(int i=P.size();i--;)P[i]&&(P[i]=Mod-P[i]);
	return P;
}
inline int Eval(poly&P,int x){
	int z=0;
	for(int i=P.size();i--;)z=((LL)z*x+P[i])%Mod;
	return z;
}
inline poly invLinear(poly P){
	const int n=P.size();
	poly Q(n+1,1);
	for(int i=0;i<n;++i)Q[i+1]=(LL)Q[i]*P[i]%Mod;
	int t=qpow(Q[n],Mod-2);Q.pop_back();
	for(int i=n;i--;)Q[i]=(LL)Q[i]*t%Mod,t=(LL)t*P[i]%Mod;
	return Q;
}
inline void extend(const int&n){
    if(Grt.empty())Grt.emplace_back(trans(1)),iGrt.emplace_back(trans(1));
    if((int)Grt.size()<n){
        int L=Grt.size();
        for(Grt.resize(n),iGrt.resize(n);L<n;L*=2){
            const int w=qpow(G,Mod/(L*4)),iw=qpow(w,Mod-2);
            for(int i=0;i<L;++i)Grt[i+L]=trans(mul(Grt[i],w)),iGrt[i+L]=trans(mul(iGrt[i],iw));
        }
    }
}
template<int A,int B,int C=0,class fun>inline void Butterrep(int i,int j,int k,fun F){
    if(A!=C)F(i,j+C/B,k+C*2-C%B),Butterrep<A,B,C+(C<A)>(i,j,k,F);
}
template<int i,class fun>inline void Butter(int n,fun F){
    if(n>32)for(int j=0;2*i*j<n;j+=32/i)Butterrep<32,i>(i,j,2*i*j,F);
    else if(i<n)for(int j=0;2*i*j<n;++j)for(int k=0;k<i;++k)F(i,j,k+2*i*j);
}
template<class T>inline void DFT(T P,int n){
    extend(n);
    const auto F=[&](int x,int y,int z){const int a=P[z],b=mul(P[z+x],Grt[y]);P[z]=add(a,b),P[z+x]=sub(a,b);};
    for(int i=n>>1;i>16;i>>=1)for(int j=0;2*i*j<n;++j)for(int k=0;k<i;k+=32)Butterrep<32,32>(i,j,k+2*i*j,F);
    Butter<16>(n,F),Butter<8>(n,F),Butter<4>(n,F),Butter<2>(n,F),Butter<1>(n,F);
}
template<class T>inline void IDFT(T P,int n){
    const uLL ni=trans(Mod-(Mod-1)/n);
	for(int i=0;i<n;++i)P[i]=mul(P[i],ni);
    extend(n);
    const auto F=[&](int x,int y,int z){const int a=P[z],b=P[z+x];P[z]=add(a,b),P[z+x]=mul(a-b+Mod,iGrt[y]);};
    Butter<1>(n,F),Butter<2>(n,F),Butter<4>(n,F),Butter<8>(n,F),Butter<16>(n,F);
    for(int i=32;i<n;i<<=1)for(int j=0;2*i*j<n;++j)for(int k=0;k<i;k+=32)Butterrep<32,32>(i,j,k+2*i*j,F);
}
template<class T>inline void rDFT(T P,int n){
    extend(n);
    const auto F=[&](int x,int y,int z){const int a=P[z],b=mul(P[z+x],Grt[y]);P[z]=add(a,b),P[z+x]=sub(a,b);};
    for(int i=n>>1,t=1;i;i>>=1,t<<=1)for(int j=0;2*i*j<n;++j)for(int k=0;k<i;++k)F(i,j+t,k+2*i*j);
}
template<class T>inline void rIDFT(T P,int n){
    const uLL ni=trans(Mod-(Mod-1)/n);
	for(int i=0;i<n;++i)P[i]=mul(P[i],ni);
    extend(n);
    const auto F=[&](int x,int y,int z){const int a=P[z],b=P[z+x];P[z]=add(a,b),P[z+x]=mul(a-b+Mod,iGrt[y]);};
    for(int i=1,t=n>>1;i<n;i<<=1,t>>=1)for(int j=0;2*i*j<n;++j)for(int k=0;k<i;++k)F(i,j+t,k+2*i*j);
}
inline void DFT(poly&P){DFT(P.begin(),P.size());}
inline void IDFT(poly&P){IDFT(P.begin(),P.size());}
inline void rDFT(poly&P){rDFT(P.begin(),P.size());}
inline void rIDFT(poly&P){rIDFT(P.begin(),P.size());}
inline poly Mul(poly P,poly Q){
    if(P.empty()||Q.empty())return poly();
	const int pn=P.size(),qn=Q.size(),rn=pn+qn-1;
	if(min(pn,qn)<=32||max(pn,qn)<=64){
		if(pn<=qn){
			vector<uLL>H(rn);
			for(int i=0;i<pn;++i){
				if(i%8==0)for(int j=qn;j--;)(H[i+j]+=1ll*P[i]*Q[j])>=(Mod2<<3)&&(H[i+j]-=Mod2<<3);
				else for(int j=qn;j--;)H[i+j]+=1ll*P[i]*Q[j];
			}
			Q.resize(rn);
			for(int i=rn;i--;)Q[i]=H[i]%Mod;
			return Q;
		}
		else{
			vector<uLL>H(rn);
			for(int i=0;i<qn;++i){
				if(i%8==0)for(int j=pn;j--;)(H[i+j]+=1ll*Q[i]*P[j])>=(Mod2<<3)&&(H[i+j]-=Mod2<<3);
				else for(int j=pn;j--;)H[i+j]+=1ll*Q[i]*P[j];
			}
			P.resize(rn);
			for(int i=rn;i--;)P[i]=H[i]%Mod;
			return P;
		}
	}
	if(rn<=256){
		const int k=max(pn,qn)/2;
		poly A=(k<pn?poly(P.begin()+k,P.end()):poly());
		poly B=(k<pn?poly(P.begin(),P.begin()+k):P);
		poly C=(k<qn?poly(Q.begin()+k,Q.end()):poly());
		poly D=(k<qn?poly(Q.begin(),Q.begin()+k):Q);
		poly AC=Mul(A,C),BD=Mul(B,D),H=Sub(Mul(Add(A,B),Add(C,D)),Add(AC,BD));
		AC.insert(AC.begin(),k*2,0),H.insert(H.begin(),k,0);
		H=Add(AC,Add(H,BD));
		return H.resize(rn),H;
	}
	const int m=2<<__lg(max(1,rn-1));
	P.resize(m),Q.resize(m);
	DFT(P),DFT(Q);
	for(int i=m;i--;)P[i]=(LL)P[i]*Q[i]%Mod;
	IDFT(P);
	return P.resize(rn),P;
}
inline poly MulT(poly P,poly Q){
    if(P.empty()||Q.empty())return poly();
	reverse(Q.begin(),Q.end());
	const int pn=P.size(),qn=Q.size(),m=2<<__lg(max(1,pn-1));
	P.resize(m),Q.resize(m);
	DFT(P),DFT(Q);
	for(int i=m;i--;)P[i]=(LL)P[i]*Q[i]%Mod;
	IDFT(P);
	return poly(P.begin()+qn-1,P.begin()+pn);
}
inline poly Inv(poly P){
	const int pn=P.size();
	const int m=2<<__lg(max(1,pn-1));
	P.resize(m);
	poly Q({qpow(P[0],Mod-2)}),F,dQ;
	Q.reserve(m);
	for(int n=1;n<m;n*=2){
		F=poly(P.begin(),P.begin()+n*2),dQ=Q;
		dQ.resize(n*2),DFT(dQ),DFT(F);
		for(int i=0;i<n*2;++i)F[i]=(LL)(Mod-F[i])*dQ[i]%Mod;
		IDFT(F),fill_n(F.begin(),n,0),DFT(F);
		for(int i=0;i<n*2;++i)dQ[i]=(LL)F[i]*dQ[i]%Mod;
		IDFT(dQ),Q.insert(Q.end(),dQ.begin()+n,dQ.end());
	}
	return Q.resize(pn),Q;
}
inline poly Quo(poly F,poly P){
	const int pn=P.size();
	if(pn<=64){
		const uLL r=trans(qpow(P[0],Mod-2));
		for(int i=0;i<pn;++i){
			LLL v=F[i];
			for(int j=0;j<i;++j)v-=(LLL)F[j]*P[i-j];
			if((F[i]=v%Mod)<0)F[i]+=Mod;
			F[i]=mul(F[i],r);
		}
		return F;
	}
	const int m=2<<__lg(max(1,(pn-1)/16)),L=(pn-1)/m+1;
	P.resize(m*L),F.resize(m*L);
	poly H(F.begin(),F.begin()+m),Q=Inv(poly(P.begin(),P.begin()+m));
	vector<poly>A(L),B(L-1);
	Q.resize(m*2),H.resize(m*2),DFT(Q),DFT(H);
	for(int i=0;i<m*2;++i)H[i]=(LL)H[i]*Q[i]%Mod;
	IDFT(H),H.resize(m);
	A[0]=poly(P.begin(),P.begin()+m),A[0].resize(m*2),DFT(A[0]);
	for(int k=1;k<L;++k){
		A[k]=poly(P.begin()+k*m,P.begin()+(k+1)*m),A[k].resize(m*2),DFT(A[k]);
		B[k-1]=poly(H.begin()+(k-1)*m,H.begin()+k*m),B[k-1].resize(m*2),DFT(B[k-1]);
		poly C(m*2);
		for(int j=0;j<k;++j){
			for(int i=0;i<m;++i)C[i]=(C[i]+(LL)(A[k-j][i]+A[k-1-j][i])*(Mod-B[j][i]))%Mod;
			for(int i=m;i<m*2;++i)C[i]=(C[i]+(LL)(A[k-j][i]+Mod-A[k-1-j][i])*(Mod-B[j][i]))%Mod;
		}
		IDFT(C),fill_n(C.begin()+m,m,0),C=Add(C,poly(F.begin()+k*m,F.begin()+(k+1)*m)),DFT(C);
		for(int i=0;i<m*2;++i)C[i]=(LL)C[i]*Q[i]%Mod;
		IDFT(C),H.insert(H.end(),C.begin(),C.begin()+m);
	}
	return H.resize(pn),H;
}
inline int Sqrt(const int&n){
	if(qpow(n,(Mod-1)/2)!=1)return -1;
	int a=1;
	while(qpow(((LL)a*a+Mod-n)%Mod,(Mod-1)/2)==1)
		a=uniform_int_distribution<int>(0,Mod-1)(rng);
	const int b=((LL)a*a+Mod-n)%Mod;
	pair<int,int>z(1,0),r(a,1);
	const auto mul=[&](pair<int,int>x,pair<int,int>y){
		return make_pair(((LL)x.first*y.first+(LL)x.second*y.second%Mod*b)%Mod,((LL)x.first*y.second+(LL)x.second*y.first)%Mod);
	};
	for(int y=(Mod+1)/2;y;(y>>=1)&&(r=mul(r,r),1))if(y&1)z=mul(z,r);
	if(z.first<0)z.first+=Mod;
	return min(z.first,Mod-z.first);
}
inline poly Sqrt(poly P){
	if(P[0]!=1){
		const int n=P.size();
		int p=0;while(p<n&&!P[p])++p;
		if(p>=n)return P;
		if(p&1)return poly({-1});
		const int v=Sqrt(P[p]);
		if(v==-1)return poly({-1});
		P.erase(P.begin(),P.begin()+p),P.resize(n-p/2);
		P=Mulx(Sqrt(Mulx(P,qpow(P[0],Mod-2))),v);
		return P.insert(P.begin(),p/2,0),P;
	}
	const int pn=P.size();
	const int m=2<<__lg(max(1,pn-1));
	P.resize(m);
	poly Q({1}),H({1}),dQ({Q[0]}),dH,nH;
	Q.reserve(m),H.reserve(m),dQ.reserve(m);
	for(int n=1;n<m;n*=2){
        dH=H;
		for(int i=0;i<n;++i)dQ[i]=(LL)dQ[i]*dQ[i]%Mod;
		IDFT(dQ),dQ=Sub(Sub(dQ,poly(P.begin(),P.begin()+n)),poly(P.begin()+n,P.begin()+n*2));
		dQ.resize(n*2),dH.resize(n*2),DFT(dH),DFT(dQ);
		for(int i=0;i<n*2;++i)dQ[i]=div2((LL)(Mod-dQ[i])*dH[i]%Mod);
		IDFT(dQ);
		Q.insert(Q.end(),dQ.begin(),dQ.begin()+n);
		if(n*2==m)break;
		dQ=Q,DFT(dQ);
		nH.resize(n*2);
		for(int i=0;i<n*2;++i)nH[i]=(LL)(Mod-dQ[i])*dH[i]%Mod;
		IDFT(nH),fill_n(nH.begin(),n,0),DFT(nH);
		for(int i=0;i<n*2;++i)dH[i]=(LL)nH[i]*dH[i]%Mod;
		IDFT(dH),H.insert(H.end(),dH.begin()+n,dH.end());
	}
	return Q.resize(pn),Q;
}
inline poly Sqrti(poly P){
	const int v=Sqrt(P[0]);
	if(v==-1)return poly({-1});
	const int pn=P.size();
	const int m=2<<__lg(max(1,pn-1));
	poly Q({qpow(v,Mod-2)});
	for(int n=1;n<m;n*=2){
		poly dQ(Q),F(P.begin(),P.begin()+n*2);
		dQ.resize(n*4),F.resize(n*4),DFT(F),DFT(dQ);
		for(int i=0;i<n*4;++i)dQ[i]=div2((Mod+1-(LL)F[i]*dQ[i]%Mod*dQ[i]%Mod)*dQ[i]%Mod);
		IDFT(dQ),Q.insert(Q.end(),dQ.begin()+n,dQ.begin()+n*2);
	}
	return Q.resize(pn),Q;
}
inline poly Direv(poly P){
    const int n=P.size();
	for(int i=1;i<n;++i)P[i-1]=(LL)P[i]*i%Mod;
	return P.pop_back(),P;
}
inline poly Integ(poly P){
    P.emplace_back(0);
	const int n=P.size();Init(n);
	for(int i=n;--i;)P[i]=(LL)P[i-1]*inv[i]%Mod;
	return P[0]=0,P;
}
inline poly Ln(poly P){
	const int n=P.size();
	poly Q=Direv(P);Q.resize(n),Q=Quo(Q,P);
	return Q.resize(n-1),Integ(Q);
}
template<bool op>inline pair<poly,poly>Expi(poly P){
	const int pn=P.size();
	const int m=2<<__lg(max(1,pn-1));
	P.resize(m);
	poly Q({1}),H({1}),dQ({1}),nF,nQ,dH,dnF;
	Q.reserve(m),H.reserve(m),dQ.reserve(m);
	for(int n=1;n<m;n*=2){
		nF=Direv(poly(P.begin(),P.begin()+n)),dnF=nF,dnF.resize(n),DFT(dnF),nQ.resize(n);
		for(int i=0;i<n;++i)nQ[i]=(LL)dnF[i]*dQ[i]%Mod;
		IDFT(nQ),nQ=Sub(Direv(Q),nQ),nQ.insert(nQ.begin(),n,0),swap(nQ[n-1],nQ[n*2-1]);
		DFT(nQ),dH=H,dH.resize(n*2),DFT(dH);
		for(int i=0;i<n*2;++i)nQ[i]=(LL)nQ[i]*dH[i]%Mod;
		IDFT(nQ),copy(nF.begin(),nF.end(),nQ.begin());
		nQ=Sub(Integ(nQ),poly(P.begin(),P.begin()+n*2)),nQ.resize(n*2),DFT(nQ);
		dQ.insert(dQ.end(),Q.begin(),Q.end()),rDFT(dQ.begin()+n,n);
		for(int i=0;i<n*2;++i)nQ[i]=(LL)(Mod-nQ[i])*dQ[i]%Mod;
		IDFT(nQ),Q.insert(Q.end(),nQ.begin()+n,nQ.end());
		if(!op&&n*2==m)break;
		dQ=Q,DFT(dQ);
		for(int i=0;i<n*2;++i)nQ[i]=(LL)(Mod-dQ[i])*dH[i]%Mod;
		IDFT(nQ),fill_n(nQ.begin(),n,0),DFT(nQ);
		for(int i=0;i<n*2;++i)nQ[i]=(LL)nQ[i]*dH[i]%Mod;
		IDFT(nQ),H.insert(H.end(),nQ.begin()+n,nQ.end());
	}
	return Q.resize(pn),H.resize(pn),make_pair(Q,H);
}
inline poly Exp(poly P){
	const int pn=P.size();
	if(pn<=64)return Expi<0>(P).first;
	const int m=2<<__lg(max(1,(pn-1)/16)),L=(pn-1)/m+1;
	auto [Q,H]=Expi<1>(poly(P.begin(),P.begin()+m));
	H.resize(m*2),DFT(H);
	vector<poly>A(L),B(L-1);
	P.resize(m*L),Init(m*(L+1));
	for(int i=0;i<pn;++i)P[i]=(LL)P[i]*i%Mod;
	A[0]=poly(P.begin(),P.begin()+m),A[0].resize(m*2),DFT(A[0]);
	for(int k=1;k<L;++k){
		A[k]=poly(P.begin()+k*m,P.begin()+(k+1)*m),A[k].resize(m*2),DFT(A[k]);
		B[k-1]=poly(Q.begin()+(k-1)*m,Q.begin()+k*m),B[k-1].resize(m*2),DFT(B[k-1]);
		poly C(m*2);
		for(int j=0;j<k;++j){
			for(int i=0;i<m;++i)C[i]=(C[i]+(LL)(A[k-j][i]+A[k-1-j][i])*B[j][i])%Mod;
			for(int i=m;i<m*2;++i)C[i]=(C[i]+(LL)(A[k-j][i]+Mod-A[k-1-j][i])*B[j][i])%Mod;
		}
		IDFT(C),fill_n(C.begin()+m,m,0),DFT(C);
		for(int i=0;i<m*2;++i)C[i]=(LL)C[i]*H[i]%Mod;
		IDFT(C),fill_n(C.begin()+m,m,0);
		for(int i=0;i<m*2;++i)C[i]=(LL)C[i]*inv[m*k+i]%Mod;
		DFT(C);
		for(int i=0;i<m*2;++i)C[i]=(LL)C[i]*B[0][i]%Mod;
		IDFT(C),Q.insert(Q.end(),C.begin(),C.begin()+m);
	}
	return Q.resize(pn),Q;
}
inline poly Qpow(poly P,int k){
	return Exp(Mulx(Ln(P),k));
}
inline poly SafePow(poly P,int k_mod_p,int k_mod_phi,int k_chk_mn){
	const int n=P.size();
	int i=0;while(i<n&&!P[i])++i;
	if(1ll*i*k_chk_mn>=n)return poly(n);
	P=poly(P.begin()+i,P.begin()+i+(n-i*k_chk_mn));
	const int r=P[0];P=Mulx(P,qpow(r,Mod-2));
	P=Qpow(P,k_mod_p),P=Mulx(P,qpow(r,k_mod_phi));
	return P.insert(P.begin(),i*k_chk_mn,0),P;
}
template<class T>inline poly SafePow(poly P,T k){
	return SafePow(P,k%Mod,k%(Mod-1),k<P.size()?k:P.size());
}
inline poly Shift(poly P,int k){
	if(!k)return P;
	const int n=P.size();
	Init(n);
	for(int i=0;i<n;++i)P[i]=(LL)frc[i]*P[i]%Mod;
	poly Q(n,1);
	for(int i=1;i<n;++i)Q[i]=(LL)Q[i-1]*k%Mod*inv[i]%Mod;
	P.resize(n+n-1),Q=MulT(P,Q);
	for(int i=0;i<n;++i)Q[i]=(LL)Q[i]*ivf[i]%Mod;
	return Q;
}
inline poly Multi(poly P,int k){
    const uLL v=trans(k);
	const int n=P.size();
	for(int i=0,w=1;i<n;++i,w=mul(w,v))P[i]=(LL)P[i]*w%Mod;
	return P;
}
inline poly ModPow(poly X,LL k,poly P){
	const int m=P.size();
	poly nP=P;reverse(nP.begin(),nP.end()),nP=Inv(nP);
	const int L=2<<__lg(m*2-1);
	P.resize(L),nP.resize(L),DFT(P),DFT(nP);
	int Xn=X.size();
	X.resize(L),DFT(X);
	const auto MoD=[&](poly F){
		poly nF=F;
		IDFT(nF);
		nF.resize(m*2-3),reverse(nF.begin(),nF.end()),nF.resize(m-2);
		nF.resize(L),DFT(nF);
		for(int i=0;i<L;++i)nF[i]=(LL)nF[i]*nP[i]%Mod;
		IDFT(nF),nF.resize(m-2),reverse(nF.begin(),nF.end());
		nF.resize(L),DFT(nF);
		for(int i=0;i<L;++i)nF[i]=(LL)nF[i]*P[i]%Mod;
		return Sub(F,nF);
	};
	poly Q({1});
	int Qn=Q.size();
	Q.resize(L),DFT(Q);
	while(k){
		if(k&1){
			for(int i=0;i<L;++i)Q[i]=(LL)Q[i]*X[i]%Mod;
			Qn+=Xn-1;
			if(Qn>=m)Q=MoD(Q),Qn=m-1;
		}
		if(k>>=1){
			for(int i=0;i<L;++i)X[i]=(LL)X[i]*X[i]%Mod;
			Xn+=Xn-1;
			if(Xn>=m)X=MoD(X),Xn=m-1;
		}
	}
	return IDFT(Q),Q.resize(m-1),Q;
}
inline poly Comp_solve(poly&P,poly&Q,int d,int n,int v){
    if(n==1){
        poly H(d+1);
		for(int i=0,w=1;i<=d;++i)
			H[i]=(LL)Binom(d+i-1,d-1)*w%Mod,w=(LL)w*v%Mod;
        H=MulT(P,H);
		return H;
    }
	poly F(d*n*4);
	for(int i=0;i<d;++i)copy_n(Q.begin()+i*n,n,F.begin()+i*n*2);
	F[d*n*2]=1,DFT(F);
	poly H(d*n*2);
	for(int i=0;i<d*n*4;i+=2)H[i/2]=(LL)F[i]*F[i+1]%Mod;
	IDFT(H),--H[0];
	for(int i=1;i<d*2;++i)copy_n(H.begin()+i*n,n/2,H.begin()+i*(n/2));
	H.resize(d*n);
	H=Comp_solve(P,H,d*2,n/2,v);
	poly nH(d*n*2);
	for(int i=0;i<d*2;++i)copy_n(H.begin()+i*(n/2),n/2,nH.begin()+i*n);
	DFT(nH);
	for(int i=0;i<d*n*4;i+=2)swap(F[i],F[i+1]),F[i]=(LL)nH[i/2]*F[i]%Mod,F[i+1]=(LL)nH[i/2]*F[i+1]%Mod;
	IDFT(F);
	for(int i=0;i<d;++i)copy_n(F.begin()+(i+d)*n*2,n,F.begin()+i*n);
	return F.resize(d*n),F;
}
inline poly Comp(poly P,poly Q){
	if(P.empty()||Q.empty())return poly();
	const int pn=P.size(),m=2<<__lg(max(1,pn-1)),v=Q[0];
	P.resize(m+m),Q=Neg(Q),Q.resize(m);
	Q=Comp_solve(P,Q,1,m,v);
	return Q.resize(pn),Q;
}
poly Compinv(poly P){
    const int n=P.size(),t=qpow(P[1],Mod-2);
	for(int i=1,w=t;i<n;++i)P[i]=(LL)P[i]*w%Mod,w=(LL)w*t%Mod;
	const int m=2<<__lg(n-1);
	poly Q(m);Q[0]=1,P=Neg(P),P.resize(m);
	P.swap(Q);
	int d=1;
	for(int k=n-1;k;d*=2,k/=2){
		const int L=2<<__lg(d*(k+1)*4-1);
		poly nP(L),nQ(L);
		for(int i=0;i<d;++i)
			copy_n(P.begin()+i*(k+1),k+1,nP.begin()+i*(k+1)*2),
			copy_n(Q.begin()+i*(k+1),k+1,nQ.begin()+i*(k+1)*2);
		nQ[d*(k+1)*2]=1,DFT(nP),DFT(nQ);
		P.resize(L/2),Q.resize(L/2);
		if(k&1)for(int i=0;i<L;i+=2)
            P[i/2]=div2(mul(((LL)nP[i]*nQ[i+1]+(LL)(Mod-nP[i+1])*nQ[i])%Mod,iGrt[i/2])),Q[i/2]=(LL)nQ[i]*nQ[i+1]%Mod;
		else for(int i=0;i<L;i+=2)
            P[i/2]=div2(((LL)nP[i]*nQ[i+1]+(LL)nP[i+1]*nQ[i])%Mod),Q[i/2]=(LL)nQ[i]*nQ[i+1]%Mod;
		IDFT(P),IDFT(Q);
		if(d*(k+1)*4>=L)--Q[d*(k+1)*4%L];
		for(int i=1;i<d*2;++i)
			copy_n(P.begin()+i*(k+1),k/2+1,P.begin()+i*(k/2+1)),
			copy_n(Q.begin()+i*(k+1),k/2+1,Q.begin()+i*(k/2+1));
		P.resize(d*2*(k/2+1)),Q.resize(d*2*(k/2+1));
	}
	Init(n);
	Q=P,reverse(Q.begin(),Q.end()),Q.resize(n);
    for(int i=1;i<n;++i)Q[i]=Q[i]*(n-1ll)%Mod*inv[i]%Mod;
    reverse(Q.begin(),Q.end()),Q=Mulx(Qpow(Q,Mod-inv[n-1]),t),Q.insert(Q.begin(),0);
    return Q.resize(n),Q;
}
inline poly Div(poly P,poly Q){
    const int n=P.size(),m=Q.size();
    if(n<m)return poly();
	reverse(P.begin(),P.end());
	reverse(Q.begin(),Q.end());
    P.resize(n-m+1),Q.resize(n-m+1);
	P=Quo(P,Q),reverse(P.begin(),P.end());
	return P;
}
inline pair<poly,poly>DivMod(poly P,poly Q){
    if(P.size()<Q.size())return make_pair(poly(),P);
    const int m=Q.size();
    poly H=Div(P,Q),R=H;
    P.resize(m-1),Q.resize(m-1);
    if((int)R.size()>m-1)R.resize(m-1);
    Q=Mul(Q,R),Q.resize(m-1);
	return make_pair(H,Sub_Empty(P,Q));
}
inline vector<poly>_EIBuild(poly Q){
	const int n=Q.size(),lgm=__lg(max(1,n-1))+1,m=1<<lgm;
    vector<poly>T(lgm+1,poly(m*2));
    Q.resize(m);
	for(int i=0;i<m;++i)T[0][i*2]=Mod+1-Q[i],T[0][i*2+1]=Mod-1-Q[i];
	for(int d=0,i=2;d<lgm;++d,i*=2){
        poly A(i);
		for(int j=0;j<m*2;j+=i*2){
			for(int k=0;k<i;++k)A[k]=(LL)T[d][j+k]*T[d][j+i+k]%Mod;
            if(d<lgm-1)copy_n(A.begin(),i,T[d+1].begin()+j),IDFT(A),A[0]=sub(A[0],2),rDFT(A),copy_n(A.begin(),i,T[d+1].begin()+j+i);
            else IDFT(A),copy_n(A.begin(),i,T[d+1].begin()+j),T[d+1][j]=sub(T[d+1][j],1),T[d+1][i]=add(T[d+1][i],1);
        }
    }
    return T;
}
inline poly _Eval(poly P,int n,vector<poly>T){
    const int pn=P.size(),lgm=T.size()-1,m=1<<lgm;
    poly Q=T[lgm];
    if(pn>n)P=DivMod(P,poly(T[lgm].begin()+m-n,T[lgm].begin()+m+1)).second;
    P.resize(m*2),rotate(P.begin(),P.end()-1,P.end());
    reverse(Q.begin(),Q.begin()+m+1),Q.resize(m),Q=Inv(Q);
    reverse(Q.begin(),Q.end()),Q.resize(m*2),DFT(P),DFT(Q);
    for(int i=0;i<m*2;++i)Q[i]=(LL)P[i]*Q[i]%Mod;
    for(int d=lgm,i=m;d--;i>>=1){
        poly A(i);
        for(int j=0;j<m*2;j+=i*2){
            copy_n(Q.begin()+i+j,i,A.begin());
            rIDFT(A),DFT(A),copy_n(A.begin(),i,Q.begin()+i+j);
            for(int k=0;k<i;++k){
                const int w=sub(Q[j+k],Q[i+j+k]);
                Q[j+k]=(LL)w*T[d][i+j+k]%Mod,Q[i+j+k]=(LL)w*T[d][j+k]%Mod;
            }
        }
    }
    const int ni=Mod-(Mod-1)/(m+m);
    for(int i=0;i<n;++i)P[i]=(LL)(Q[i*2]-Q[i*2+1]+Mod)*ni%Mod;
    return P.resize(n),P;
}
inline poly Eval(poly P,poly Q){
	return _Eval(P,Q.size(),_EIBuild(Q));
}
inline poly Inter(poly P,poly Q){
    const int n=P.size();
    vector<poly>T=_EIBuild(P);
    const int lgm=T.size()-1,m=1<<lgm;
    P=T[lgm],P.erase(P.begin(),P.begin()+m-n),P=invLinear(_Eval(Direv(P),n,T));
    P.resize(m+m),Q.resize(m+m);
    for(int i=m;i--;)P[i*2]=P[i*2+1]=(LL)Q[i]*P[i]%Mod;
    for(int d=0,i=2;d<lgm;++d,i*=2,swap(P,Q)){
        poly A(i);
        for(int j=0;j<m+m;j+=i*2){
            for(int k=0;k<i;++k)A[k]=((LL)T[d][j+k]*P[j+i+k]+(LL)T[d][j+i+k]*P[j+k])%Mod;
            if(d<lgm-1)copy_n(A.begin(),i,Q.begin()+j),IDFT(A),rDFT(A),copy_n(A.begin(),i,Q.begin()+j+i);
            else IDFT(A),copy_n(A.begin(),i,Q.begin());
        }
    }
    return poly(P.begin()+m-n,P.begin()+m);
}
inline poly ChirpZ(poly P,int X,int m){
	if(!X){
		poly Q(m,Eval(P,0));
		return Q[0]=Eval(P,1),Q;
	}
	const int n=P.size();
    const uLL x=trans(X),y=trans(qpow(X,Mod-2));
    int pwX=1,ipwX=1;
	poly pwXX(n+m-1,1),ipwXX(n+m-1,1);
	for(int i=0;i+1<n+m;++i)
		pwXX[i+1]=(LL)pwXX[i]*pwX%Mod,ipwXX[i+1]=(LL)ipwXX[i]*ipwX%Mod,pwX=mul(pwX,x),ipwX=mul(ipwX,y);
	for(int i=0;i<n;++i)P[i]=(LL)P[i]*ipwXX[i]%Mod;
	P=MulT(pwXX,P);
	for(int i=0;i<m;++i)P[i]=(LL)P[i]*ipwXX[i]%Mod;
	return P;
}
inline poly ChirpZInter(poly P,int X){
	const int n=P.size();
	if(n<2)return P;
    const uLL x=trans(X),y=trans(qpow(X,Mod-2));
	poly pwXX(n+n-1,1),ipwXX(n+n-1,1);
    int pwX=1,ipwX=1;
	for(int i=0;i+1<n+n;++i)
		pwXX[i+1]=(LL)pwXX[i]*pwX%Mod,ipwXX[i+1]=(LL)ipwXX[i]*ipwX%Mod,pwX=mul(pwX,x),ipwX=mul(ipwX,y);
	poly Q(n,1);
    int t=X;
	for(int i=1;i<n;++i)Q[i]=(LL)(Mod+1-t)*Q[i-1]%Mod,t=mul(t,x);
	t=(LL)(Mod+1-t)*Q[n-1]%Mod;
	Q=invLinear(Q);
	for(int i=0;i<n;++i)
		P[i]=(LL)(i&1?Mod-P[i]:P[i])*pwXX[n-1-i]%Mod*ipwXX[n-1]%Mod*Q[i]%Mod*Q[n-1-i]%Mod*ipwXX[i]%Mod;
	P=MulT(pwXX,P);
	for(int i=0;i<n;++i)P[i]=(LL)P[i]*ipwXX[i]%Mod;
	poly H(n,1);
	for(int i=1;i<n;++i)
		H[i]=(LL)(i&1?Mod-t:t)*pwXX[i]%Mod*Q[i]%Mod*Q[n-i]%Mod;
	P=Mul(P,H),P.resize(n),reverse(P.begin(),P.end());
	return P;
}
inline poly PointShift(poly P,int l,int r){
	const int n=P.size();Init(n);
	if(l<n){
		if(r<n)return poly(P.begin()+l,P.begin()+r+1);
		else{
			poly Q=PointShift(P,n,r);
			Q.insert(Q.begin(),P.begin()+l,P.end());
			return Q;
		}
	}
	if(r>=Mod){
		r-=Mod;
		poly Q=PointShift(P,l,Mod-1);
		if(r<n)Q.insert(Q.end(),P.begin(),P.begin()+r+1);
		else Q.insert(Q.end(),P.begin(),P.end()),P=PointShift(P,n,r),Q.insert(Q.end(),P.begin(),P.end());
		return Q;
	}
	poly Q(r-l+n),H(n);
	for(int i=0;i<n;++i)H[i]=(LL)((n-1-i)&1?Mod-P[i]:P[i])*ivf[i]%Mod*ivf[n-1-i]%Mod;
	for(int i=0;i<r-l+n;++i)Q[i]=l-n+i+1;
	Q=invLinear(Q),reverse(H.begin(),H.end()),Q=MulT(Q,H);
	poly fac(r-l+1+n);
	fac[0]=1;
	for(int i=0;i<r-l+n;++i)fac[i+1]=max(1ll,(LL)fac[i]*(l+i-n+1)%Mod);
	poly ifac=invLinear(fac);
	for(int i=0;i<=r-l;++i){
		const int p=(i+l)%Mod;
		if(p>=0&&p<n)Q[i]=P[p];
		else Q[i]=(LL)Q[i]*ifac[i]%Mod*fac[i+n]%Mod;
	}
	return Q;
}
inline Mat2 operator*(const Mat2&x,const Mat2&y){
	return Mat2(
		Add_Empty(Mul(get<0>(x),get<0>(y)),Mul(get<1>(x),get<2>(y))),
		Add_Empty(Mul(get<0>(x),get<1>(y)),Mul(get<1>(x),get<3>(y))),
		Add_Empty(Mul(get<2>(x),get<0>(y)),Mul(get<3>(x),get<2>(y))),
		Add_Empty(Mul(get<2>(x),get<1>(y)),Mul(get<3>(x),get<3>(y)))
	);
}
inline Mat2 Hgcd(poly P,poly Q,int d){
    if(P.size()<Q.size())return Hgcd(Q,P,d)*Mat2(poly(),poly({1}),poly({1}),poly());
    d=min(d,(int)P.size()-1);
    if(Q.empty()||Q.size()<P.size()-d)return Mat2(poly({1}),poly(),poly(),poly({1}));
    const int m=P.size()-d*2-1;
    if(m>0)P=poly(P.begin()+m,P.end()),Q=poly(Q.begin()+m,Q.end());
    if(!d)return Mat2(poly(),poly({1}),poly({1}),Neg(Div(P,Q)));
    const Mat2 M=Hgcd(P,Q,d/2);
    const poly H=Add_Empty(Mul(get<2>(M),P),Mul(get<3>(M),Q));
    if(H.size()<P.size()-d)return M;
    const poly R=Add_Empty(Mul(get<0>(M),P),Mul(get<1>(M),Q));
    const auto [A,B]=DivMod(R,H);
    return Hgcd(H,B,H.size()-P.size()+d)*Mat2(poly(),poly({1}),poly({1}),Neg(A))*M;
}
inline tuple<poly,poly,poly>Exgcd(poly P,poly Q){
	Empty(P),Empty(Q);
    const Mat2 M=Hgcd(P,Q,max(P.size(),Q.size())-1);
    const poly H=Add_Empty(Mul(get<0>(M),P),Mul(get<1>(M),Q));
    const int v=qpow(H.back(),Mod-2);
    return make_tuple(Mulx(get<0>(M),v),Mulx(get<1>(M),v),Mulx(H,v));
}
inline poly Gcd(poly P,poly Q){
	return get<2>(Exgcd(P,Q));
}
inline poly Modinv(poly P,poly Q){
	const auto [W,_,D]=Exgcd(P,Q);
	return D.size()>1?poly({-1}):W;
}
inline poly operator*(poly P,poly Q){return Mul(P,Q);}
inline poly operator*(poly P,int x){return Mulx(P,x);}
inline poly operator*(int x,poly P){return Mulx(P,x);}
inline poly operator+(poly P,poly Q){return Add(P,Q);}
inline poly operator-(poly P,poly Q){return Sub(P,Q);}
inline poly operator-(poly P){return Neg(P);}
inline poly operator/(poly P,poly Q){return Div(P,Q);}
inline poly operator%(poly P,poly Q){return DivMod(P,Q).second;}
inline poly&operator*=(poly&P,poly Q){return P=Mul(P,Q);}
inline poly&operator*=(poly&P,int x){return P=Mulx(P,x);}
inline poly&operator+=(poly&P,poly Q){return P=Add(P,Q);}
inline poly&operator-=(poly&P,poly Q){return P=Sub(P,Q);}
inline poly&operator/=(poly&P,poly Q){return P=Div(P,Q);}
inline poly&operator%=(poly&P,poly Q){return P=DivMod(P,Q).second;}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n;cin>>n;
	poly f(n),g(n);
	g[1]=1;
	for(int i=0;i<n;i++)cin>>f[i];
	int b=(Mod+1)/2;
	while(b)
	{
		if(b&1)g=Comp(g,f);
		f=Comp(f,f),b/=2;
	}
	for(int i=0;i<n;i++)printf("%d ",g[i]);
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int qpow(int, int, int)’:
Main.cpp:22:9: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
   22 |         for(;y;(y>>=1)&&(x=(LL)x*x%Mod))if(y&1)z=(LL)z*x%Mod;return z;
      |         ^~~
Main.cpp:22:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘for’
   22 |         for(;y;(y>>=1)&&(x=(LL)x*x%Mod))if(y&1)z=(LL)z*x%Mod;return z;
      |                                                              ^~~~~~

ジャッジ結果