代码

#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>

using namespace std;

typedef long long ll;

const int N = 2100005, M = 8400005, P = 998244353, g = 3, G = 25;

int fxt (int x) { int l = 1; while (l <= x) l <<= 1; return l; }
int fpow (int a, int t) {
	static int r;
	for (r = 1; t; t >>= 1, a = (ll)a * a % P) if (t & 1) r = (ll)r * a % P;
	return r;
}
int pol[M], *ed = pol, *ww[G], *iww[G], *_w;
int *nint (int len) { int *r = ed; ed += len; return r; }
void init (int n) {
	register int i, j, k, w, iw;
	for (i = j = 1; j <= n; i ++, j <<= 1) {
		ww[i] = nint(j), iww[i] = nint(j), ww[i][0] = iww[i][0] = 1;
		w = fpow(g, (P - 1) >> i), iw = fpow(w, P - 2);
		for (k = 1; k < j; k ++) ww[i][k] = (ll)ww[i][k - 1] * w % P, iww[i][k] = (ll)iww[i][k - 1] * iw % P;
	}
}
void fft (int a[], int n, int dft) {
	register int i, j, k, l, c = 0, u, v;
	for (i = 1, j = n >> 1; i < n - 1; i ++) {
		if (i < j) a[i] ^= a[j] ^= a[i] ^= a[j];
		for (k = n >> 1; (j ^= k) < k; k >>= 1);
	}
	for (l = 2, c = 1; l <= n; l <<= 1, c ++) {
		_w = dft == -1 ? iww[c] : ww[c];
		for (i = l >> 1, j = 0; j < n; j += l) for (k = 0; k < i; k ++) {
			u = a[j + k] % P, v = (ll)a[j + k + i] * _w[k] % P;
			a[j + k] = u + v, a[j + k + i] = u - v;
		}
	}
	if (dft == -1) for (v = fpow(n, P - 2), i = 0; i < n; i ++) a[i] = (ll)a[i] * v % P;
	for (i = 0; i < n; i ++) a[i] = (a[i] % P + P) % P;
}
int x[N], y[N], z[N];

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
	int l = fxt(n + m), i;
	init(l), memcpy(x, a, (n + 1) << 2), memcpy(y, b, (m + 1) << 2);
	fft(x, l, 1), fft(y, l, 1);
	for (i = 0; i < l; i ++) z[i] = (ll)x[i] * y[i] % P;
	fft(z, l, -1);
	for (i = 0; i <= n + m; i ++) c[i] = z[i];
}

评测结果