代码

#include <algorithm>

const int N = 1 << 21; const int _N = N >> 1;
const int p = 81 << 21 | 1;

unsigned w[N + 1];
unsigned ntt_sup[N];
inline void ntt(auto a[]) {
	auto b = ntt_sup, j = a, _j = a; int _n = N >> 1, i, k, _k; auto _w = w;
	for(i = 1; i < N; i <<= 1, std :: swap(a, b))
		for(k = 0, j = a, _j = a + _n, _w = w; k != N; k += i, _w += i)
			for(_k = k, k += i; _k != k; ++j, ++_j, ++_k)
				b[_k] = *j + *_j < p ? *j + *_j : *j + *_j - p,
				b[_k + i] = (long long)(*j - *_j + p) * *_w % p;
	std :: copy(a, a + N, b);
}

inline void intt(auto a[]) {
	auto b = ntt_sup, j = a, _j = a; int _n = N >> 1, i, k, _k; auto _w = w;
	for(i = 1; i < N; i <<= 1, std :: swap(a, b))
		for(k = 0, j = a, _j = a + _n, _w = w + N; k != N; k += i, _w -= i)
			for(_k = k, k += i; _k != k; ++j, ++_j, ++_k)
				b[_k] = *j + *_j < p ? *j + *_j : *j + *_j - p,
				b[_k + i] = (long long)(*j - *_j + p) * *_w % p;
	std :: copy(a, a + N, b);
}

unsigned a[N], b[N];
void poly_multiply(unsigned *aa, int n, unsigned *bb, int m, unsigned *c) {
	w[0] = 1; for(int i = 1; i <= N; ++i) w[i] = (long long)w[i - 1] * 154249541 % p;
	
	std :: copy(aa, aa + n + 1, a), std :: copy(bb, bb + m + 1, b);
	m += n; for(n = 1; n <= m; n <<= 1); ++m;
	ntt(a), ntt(b); for(int i = 0; i < n; ++i) a[i] = (long long)a[i] * b[i] % p; intt(a);
	for(int i = 0; i < m; ++i) c[i] = (long long)a[i] * 169869232 % p;
}

评测结果