代码

// http://uoj.ac/submission/9660
// 从 UOJ 上抄代码好开心啊……

#define if if (
#define then )
#define do )
#define for for (
#define while while (
#define begin {
#define end }

const int mo=104857601;
const int _g=3,_g_inv=34952534;

int wn[2][30];

inline int qpow(int a,int b,int p)
begin
	while p do begin
		if p&1 then a=1LL*a*b%mo;
		b=1LL*b*b%mo;
		p>>=1;
	end;
	return a;
end;

inline int getinv(int x)
begin
	return qpow(1,x,mo-2);
end;

inline void FFT_init()
begin
	int i;
	for i=1;i<=25;i++ do begin
		wn[0][i]=qpow(1,_g,(mo-1)>>i);
		wn[1][i]=qpow(1,_g_inv,(mo-1)>>i);
	end;
end;

inline int bitrev(int x,int lgN)
begin
	int ret=0;
	int i;
	for i=0;i<lgN;i++ do ret|=((x>>i)&1)<<(lgN-1-i);
	return ret;
end;

template <class T> inline void swap(T &a, T &b) {T c = a; a = b; b = c;}

inline void FFT(int *a,int lgN,bool rev)
begin
	int i,j,k;
	int N=1<<lgN;
	for i=0;i<N;i++ do begin
		int t=bitrev(i,lgN);
		if i<t then swap(a[i],a[t]);
	end;
	for i=0;i<lgN;i++ do begin
		int t=1<<i;
		int ww=wn[rev][i+1];
		for j=0;j+t<N;j+=t+t do begin
			int *A=a+j;
			int w=1;
			for k=0;k<t;k++ do begin
				long long tmp=1LL*A[k+t]*w;
				A[k+t]=(A[k]-tmp)%mo;
				A[k]=(A[k]+tmp)%mo;
				w=1LL*w*ww%mo;
			end;
		end;
	end;
	for i=0;i<N;i++ do a[i]=(a[i]+mo)%mo;
	if rev then begin
		int tmp=getinv(N);
		for i=0;i<N;i++ do a[i]=1LL*a[i]*tmp%mo;
	end;
end;

#define M (1<<20)

int n,m;
int a[M*2],b[M*2];

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
	++n;++m;
	FFT_init();
	int i;
	for i=0;i<n;i++ do ::a[i] = a[i];
	for i=0;i<m;i++ do ::b[i] = b[i];
	int t=1;
	while (1<<t)<n+m do ++t;
	FFT(::a,t,0);FFT(::b,t,0);
	for i=0;i<(1<<t);i++ do ::a[i]=1LL*::a[i]*::b[i]%mo;
	FFT(::a,t,1);
	for i=0;i<n+m-1;i++ do c[i] = ::a[i];
}

评测结果