代码

#include <bits/stdc++.h>
using namespace std;








typedef int i32;
typedef long long i64;
typedef unsigned int u32;
typedef unsigned long long u64;

constexpr int to_pow2(int x){
	return 1<<__lg((x<<1)-1);
}

constexpr u32 u32_inv(u32 x){
	u32 a=x;
	a*=2-a*x;
	a*=2-a*x;
	a*=2-a*x;
	a*=2-a*x;
	return a;
}
constexpr u64 u64_inv(u64 x){
	u64 a=x;
	a*=2-a*x;
	a*=2-a*x;
	a*=2-a*x;
	a*=2-a*x;
	a*=2-a*x;
	return a;
}



template<i32 mod>
struct modint{
	const static u64 b_I=0xffffffffffffffff/mod;
	const static u32 MOD=mod;
	const static u32 m_I=-u32_inv(mod);
	u32 x;
	modint():x(0){}
	template<typename T>
	modint(T x_){
		if(is_unsigned<T>::value){
			x_=((x_<mod)?x_:x_%mod);
			x=x_;
		}
		else{
			x_=((x_>=-mod)&&(x_<mod)?x_:x_%mod);
			if(x_<0) x_+=mod;
			x=x_;
		}
		x=((u64)x<<32)-((x*b_I)>>32)*mod;
		x=min(x,x-mod);
	}
	static modint _raw(u32 x_){
		modint z;
		z.x=x_;
		return z;
	}
	modint operator +(modint t) const{return _raw(min(x+t.x,x+t.x-mod));}
	modint& operator +=(modint t){return *this=*this+t;}
	modint operator -(modint t) const{return _raw(min(x-t.x,x-t.x+mod));}
	modint& operator -=(modint t){return *this=*this-t;}
	modint operator -() const{return _raw(min(-x,-x+mod));}
	modint operator *(modint t) const{
		u32 o=((u64)x*t.x+(u64)(x*t.x*m_I)*mod)>>32;
		return _raw(min(o,o-mod));
	}
	modint& operator *=(modint t){return *this=*this*t;}
	template<typename T>
	modint pow(T y) const{
		modint w=*this,z=modint(1);
		while(y){
			if(y&1) z*=w;
			w*=w;
			y>>=1;
		}
		return z;
	}
	modint inv() const{
		return pow(mod-2);
	}
	modint operator /(modint t) const{return *this*t.inv();}
	modint& operator /=(modint t){return *this=*this/t;}
	template<typename T>
	modint operator ^(T x) const{return pow(x);}
	template<typename T>
	modint& operator ^=(T x){return *this=*this^x;}
	friend istream& operator >>(istream &in,modint& x){i64 w;in>>w;x=w;return in;}
	friend ostream& operator <<(ostream &out,modint x){return out<<x.val();}
	u32 val() const{
		u32 o=(x+(u64)(x*m_I)*mod)>>32;
		return min(o,o-mod);
	}
};



constexpr int mod=469762049;
typedef modint<mod> mint;
const mint g=3,ig=156587350;



vector<mint>& operator +=(vector<mint>& lhs,vector<mint>& rhs){
	for(int i=0;i<(int)lhs.size();++i) lhs[i]+=rhs[i];
	return lhs;
}
vector<mint> operator +(vector<mint> lhs,vector<mint>& rhs){
	return lhs+=rhs;
}

vector<mint>& operator -=(vector<mint>& lhs,vector<mint>& rhs){
	for(int i=0;i<(int)lhs.size();++i) lhs[i]-=rhs[i];
	return lhs;
}
vector<mint> operator -(vector<mint> lhs,vector<mint>& rhs){
	return lhs-=rhs;
}

vector<mint>& operator *=(vector<mint>& lhs,vector<mint>& rhs){
	for(int i=0;i<(int)lhs.size();++i) lhs[i]*=rhs[i];
	return lhs;
}
vector<mint> operator *(vector<mint> lhs,vector<mint>& rhs){
	return lhs*=rhs;
}

void rsz(vector<mint>& v,vector<mint>& res,int sz){
	if((int)v.size()<=sz){
		res=v;
		res.resize(sz);
	}
	else{
		res.assign(v.begin(),v.begin()+sz);
	}
}



vector<mint> w{mint(1)},inv{mint(0),mint(1)};
void init_w(int n){
	int limit=to_pow2(n);
	int sz=(int)w.size();
	if(limit>sz){
		w.resize(limit);
		while(sz<limit){
			mint wn=g^(((mint::MOD-1)/sz)>>2);
			for(int i=sz;i<(sz<<1);++i) w[i]=w[i-sz]*wn;
			sz<<=1;
		}
	}
}
void init_inv(int n){
	int limit=to_pow2(n+1);
	int sz=(int)inv.size();
	if(limit>sz){
		inv.resize(limit);
		for(int i=sz;i<limit;++i) inv[i]=inv[mod%i]*(mod-mod/i);
	}
}

void DIF(mint* f,int limit){
	init_w(limit);
	for(int k=limit>>1,o=limit;k;k>>=1,o>>=1){
		if(k>=4){
			mint x0,y0,x1,y1,x2,y2,x3,y3;
			for(int i=0,t=0;i<limit;i+=o,++t){
				for(int j=0;j<k;j+=4){
					x0=f[i+j+0],y0=f[i+j+k+0]*w[t];
					x1=f[i+j+1],y1=f[i+j+k+1]*w[t];
					x2=f[i+j+2],y2=f[i+j+k+2]*w[t];
					x3=f[i+j+3],y3=f[i+j+k+3]*w[t];
					f[i+j+0]=x0+y0,f[i+j+k+0]=x0-y0;
					f[i+j+1]=x1+y1,f[i+j+k+1]=x1-y1;
					f[i+j+2]=x2+y2,f[i+j+k+2]=x2-y2;
					f[i+j+3]=x3+y3,f[i+j+k+3]=x3-y3;
				}
			}
		}
		else{
			for(int i=0,t=0;i<limit;i+=o,++t){
				for(int j=0;j<k;++j){
					mint x=f[i+j],y=f[i+j+k]*w[t];
					f[i+j]=x+y,f[i+j+k]=x-y;
				}
			}
		}
	}
}
void DIT(mint* f,int limit){
	init_w(limit);
	for(int k=1,o=2;k<limit;k<<=1,o<<=1){
		if(k>=4){
			mint x0,y0,x1,y1,x2,y2,x3,y3;
			for(int i=0,t=0;i<limit;i+=o,++t){
				for(int j=0;j<k;j+=4){
					x0=f[i+j+0],y0=f[i+j+k+0];
					x1=f[i+j+1],y1=f[i+j+k+1];
					x2=f[i+j+2],y2=f[i+j+k+2];
					x3=f[i+j+3],y3=f[i+j+k+3];
					f[i+j+0]=x0+y0,f[i+j+k+0]=(x0-y0)*w[t];
					f[i+j+1]=x1+y1,f[i+j+k+1]=(x1-y1)*w[t];
					f[i+j+2]=x2+y2,f[i+j+k+2]=(x2-y2)*w[t];
					f[i+j+3]=x3+y3,f[i+j+k+3]=(x3-y3)*w[t];
				}
			}
		}
		else{
			for(int i=0,t=0;i<limit;i+=o,++t){
				for(int j=0;j<k;++j){
					mint x=f[i+j],y=f[i+j+k];
					f[i+j]=x+y,f[i+j+k]=(x-y)*w[t];
				}
			}
		}
	}
	reverse(f+1,f+limit);
	mint inv=(mint(limit)).inv();
	for(int i=0;i<limit;++i) f[i]*=inv;
}
void DIF(vector<mint>& f,int limit){
	DIF(f.data(),limit);
}
void DIF(vector<mint>& f){
	DIF(f.data(),f.size());
}
void DIT(vector<mint>& f,int limit){
	DIT(f.data(),limit);
}
void DIT(vector<mint>& f){
	DIT(f.data(),f.size());
}
void conv(vector<mint>& lhs,vector<mint>& rhs,vector<mint>& res,int n){
	init_w(n);
	int limit=to_pow2(n);
	vector<mint> f,h;
	rsz(lhs,f,limit);
	rsz(rhs,h,limit);
	DIF(f,limit);
	DIF(h,limit);
	f*=h;
	DIT(f,limit);
	res.resize(n);
	for(int i=0;i<n;++i) res[i]=f[i];
}
void conv(vector<mint>& lhs,vector<mint>& rhs,vector<mint>& res){
	conv(lhs,rhs,res,lhs.size());
}






void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c){
	vector<mint> A(a,a+n+1);
	vector<mint> B(b,b+m+1);
	vector<mint> C;
	conv(A,B,C,n+m+1);
	for(int i=0;i<n+m+1;++i) c[i]=C[i].val();
}

评测结果