代码

#include<bits/stdc++.h>
const int maxn = 1 << 18;
const int mod = 81788929; 
const int inv2 = mod + 1 >> 1;
typedef long long ll;
int n, m;
typedef unsigned long long u64;
typedef unsigned u32;
using AI = u32[maxn];
struct istream {
	static const int size = 1 << 19;
	char buf[size], *vin;
	inline istream() {
		scanf("%d%d\n",&n,&m);
		fread(buf,1,size,stdin);
		vin = buf - 1;
	}
	inline istream& operator >> (u32 & x) {
		x = *++vin & 15, ++ vin;
		return * this;
	}
} cin;

struct ostream {
	static const int size = 1 << 23;
	char buf[size], *vout;
	unsigned map[10000];
	inline ostream() {
		for(int i = 0;i < 10000;++i) 
			map[i] = i % 10 + 48 << 24 | i / 10 % 10 + 48 << 16 | i / 100 % 10 + 48 << 8 | i / 1000 + 48;
		vout = buf + size;
	}
	inline ~ ostream()
	{ fwrite(vout,1,buf + size - vout,stdout); }
	inline ostream& operator << (u32 x) {
		if(x) {
			for(;x >= 1000;x /= 10000) *--(unsigned*&)vout = map[x % 10000];
			while(x) *--vout = x % 10 + 48, x /= 10;
		} else *--vout = 48;
		return * this;
	}
	inline ostream& operator << (char x)
	{
		*--vout = x;
		return * this;
	}
} cout;
inline int pow(int a,int b,int ans = 1) {
	for(;b;b >>= 1,a = (ll) a * a % mod) if(b & 1)
		ans = (ll) ans * a % mod;
	return ans;
}
AI wn, rev, wn_;
inline u32 getinv(u32 x) { return ((u64) x << 32) / mod; }
namespace poly
{
	int lim,invlim;
	inline void init(int len) {
		for(lim = invlim = 1;lim < len;lim <<= 1) invlim = (ll) invlim * inv2 % mod;
		for(int i = 1;i < lim;++i) rev[i] = rev[i >> 1] >> 1 | (i % 2 * lim / 2);
		const int W = pow(7,mod / lim); wn[lim >> 1] = 1; wn_[lim >> 1] = getinv(1);
		for(int i = 1;i + i < lim;++i)
			wn[(lim >> 1) + i] = (u64) wn[(lim >> 1) + i - 1] * W % mod, wn_[(lim >> 1) + i] = getinv(wn[(lim >> 1) + i]);
		for(int i = lim >> 1;--i >= 1;) wn[i] = wn[i << 1], wn_[i] = wn_[i << 1];
	}
	inline void fft(u32 * a,int type) {
		for(int i = 0;i < lim;++i) if(rev[i] > i) std::swap(a[i], a[rev[i]]);
		for(int mid = 1;mid < lim;mid <<= 1) {
			if(mid <= 4) {
				for(int i = 0;i < lim;i += mid + mid) for(int j = 0;j < mid;++j) {
					const u32 x = a[i + j + mid] * wn[mid + j] - u32((u64) wn_[mid + j] * a[i + j + mid] >> 32) * mod;
					a[i + j + mid] = mod + mod - x + a[i + j]; a[i + j] += x;
				}
			} else {
#define R(j) { \
				u32 x = a[i + j + mid] * wn[mid + j] - u32((u64) wn_[mid + j] * a[i + j + mid] >> 32) * mod; a[i + j + mid] = mod + mod - x + a[i + j]; a[i + j] += x; \
			 }
				for(int i = 0;i < lim;i += mid + mid) for(int j = 0;j < mid;j += 8) {
					R(j + 0);
					R(j + 1);
					R(j + 2);
					R(j + 3);
					R(j + 4);
					R(j + 5);
					R(j + 6);
					R(j + 7);
				}
			}
		}
		if(!type) {
			for(int i = 0;i < lim;++i) a[i] = (u64) a[i] * invlim % mod;
			std::reverse(a + 1,a + lim);
		}
	}
}
AI a, b;
int main()
{
	for(int i = 0;i <= n;++i) cin >> a[i];
	for(int i = 0;i <= m;++i) cin >> b[i];
	poly::init(n + m + 1);
	poly::fft(a, 1);
	poly::fft(b, 1);
	for(int i = 0;i < poly::lim;++i) a[i] = (ll) a[i] * b[i] % mod;
	poly::fft(a, 0);
	for(int i = n + m;i >= 0;--i) cout << ' ' << a[i];
}

评测结果