代码

#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;
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 >> (int & x)
	{
		x = *++vin & 15, ++ vin;
		return * this;
	}
} cin;
struct ostream
{
	static const int size = 1 << 21;
	char buf[size], *vout;
	inline ostream()
	{ vout = buf + size; }
	inline ~ ostream()
	{ fwrite(vout,1,buf + size - vout,stdout); }
	inline ostream& operator << (int x)
	{
		do *--vout = x % 10 + 48; while(x /= 10);
		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;
}
using AI = int[maxn];
AI wn, rev;
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);
		for(int mid = 1;mid < maxn;mid <<= 1)
		{
			const int W = pow(7,mod / mid / 2); wn[mid] = 1;
			for(int i = 1;i < mid;++i) wn[mid + i] = (ll) wn[mid + i - 1] * W % mod;
		}
	}
	inline void fft(int * 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)
			for(int i = 0;i < lim;i += mid + mid)
				for(int j = 0;j < mid;++j)
				{
					const int x = (ll) a[i + j + mid] * wn[mid + j] % mod;
					a[i + j + mid] = mod - x + a[i + j]; a[i + j] += x;
				}
		for(int i = 0;i < lim;++i) a[i] %= mod;
		if(!type)
		{
			for(int i = 0;i < lim;++i) a[i] = (ll) 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];
}

评测结果