CVBB ACM Team

====== NTT ======

 $1004535809$ 的原根是 $3$ 别算了（x 

补充板子

<code cpp>

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const ll maxn = 4e6+10;
const ll inf = 1e9;
const double eps = 1e-8;
const ll mod = 998244353;

ll f[maxn],g[maxn],mxn,w[maxn],n,m,rw[maxn],t[maxn],bit,pos[maxn],s[maxn],limit;

inline ll quick_mul(ll a,ll b,ll p){
	unsigned long long c=(long double) a/p*b;
	ll ret=a*b-(unsigned long long)c*p;
	ret%=p;
	while(ret<0) ret+=p;
	return ret%p;
}
inline ll quick_power(ll a,ll b,ll p){
	ll ret=1;
	while(b){
		if(b&1) ret=quick_mul(ret,a,p);
		a=quick_mul(a,a,p);
		b>>=1;
	}
	while(ret<0) ret+=p;
	return ret%p;
}

void prepare() {
	for(int i=0;i<mxn;i++) pos[i]=pos[i>>1]>>1|((i&1)<<(limit-1));
	w[0]=1;w[1]=quick_power(3,(mod-1)/mxn,mod);
	for(int i=2;i<=mxn;i++) w[i]=1ll*w[i-1]*w[1]%mod;
	rw[0]=1,rw[1]=quick_power(quick_power(3,mod-2,mod),(mod-1)/mxn,mod);
	for(int i=2;i<=mxn;i++) rw[i]=1ll*rw[i-1]*rw[1]%mod;
}

void ntt(ll *r,ll op) {
	for(int i=1;i<mxn;i++) if(pos[i]>i) swap(r[i],r[pos[i]]);
	for(int i=1,d=mxn>>1;i<mxn;i<<=1,d>>=1) 
		for(int j=0;j<mxn;j+=i<<1)
			for(int k=0;k<i;k++) {
				int x=r[j+k],y=1ll*r[i+j+k]*(op==1?w:rw)[k*d]%mod;
				r[j+k]=(x+y)%mod,r[i+j+k]=(x-y+mod)%mod;
			}
	if(op==-1) {
		int inv=quick_power(mxn,mod-2,mod);
		for(int i=0;i<mxn;i++) r[i]=1ll*r[i]*inv%mod;
	}
}

/*void solve(ll l,ll r) {
	if(l==r) return ;
	int mid=(l+r)>>1;
	solve(l,mid);
	for(int i=l;i<=mid;i++) t[i-l]=f[i],s[i-l]=g[i-l];
	for(int i=mid+1;i<=r;i++) t[i-l]=0,s[i-l]=g[i-l];
	for(bit=0,N=1;N<=r-l;N<<=1,bit++);
	for(int i=r-l+1;i<N;i++) t[i]=s[i]=0;
	for(int i=1;i<N;i++) pos[i]=pos[i>>1]>>1|((i&1)<<(bit-1));
	ntt(s,1),ntt(t,1);
	for(int i=0;i<N;i++) s[i]=1ll*s[i]*t[i]%mod;
	ntt(s,-1);
	for(int i=mid+1;i<=r;i++) f[i]=(f[i]+s[i-l])%mod;
	solve(mid+1,r);
}*/

int main() {
	scanf("%lld %lld",&n,&m);
	for(int i=0;i<=n;i++) scanf("%lld",&f[i]);
	for(int i=0;i<=m;i++) scanf("%lld",&g[i]);
	for(mxn=1;mxn<=n+m;mxn<<=1) limit++;
	prepare();
	ntt(f,1);
	ntt(g,1);
	for(int i=0;i<=mxn;i++) f[i]=quick_mul(f[i],g[i],mod);
	ntt(f,-1);
	for(int i=0;i<=m+n;i++) printf("%lld ",f[i]);
	return 0;
}

</code>
CVBB ACM Team

用户工具

站点工具

页面工具
