3007. A * B II

C++上网找FFT模板吧
快速傅里叶变换可以在nlogn复杂度内求解多项式乘积（下面放一个卷积的模板）

include

using namespace std;

const int MOD = 998244353;
const int G = 3;

int quick_pow(int a, int b) {
if (b == 0) return 1;
if (b == 1) return a % MOD;
int res = quick_pow(a, b / 2);
res = 1LL * res * res % MOD;
if (b & 1) res = 1LL * res * a % MOD;
return res;
}

void ntt(int * a, int N, int f) {
int i, j = 0, t, k;
for (i = 1; i < N - 1; i++) {
for (t = N; j ^= t >>= 1, ~j & t;);
if (i < j) {
swap(a[i], a[j]);
}
}
for (i = 1; i < N; i <<= 1) {
t = i << 1;
int wn = quick_pow(G, (MOD - 1) / t);
for (j = 0; j < N; j += t) {
int w = 1;
for (k = 0; k < i; k++, w = 1LL * w * wn % MOD) {
int x = a[j + k], y = 1LL * w * a[j + k + i] % MOD;
a[j + k] = (x + y) % MOD, a[j + k + i] = (x - y + MOD) % MOD;
}
}
}
if (f == -1) {
reverse(a + 1, a + N);
int inv = quick_pow(N, MOD - 2);
for (i = 0; i < N; i++)
a[i] = 1LL * a[i] * inv % MOD;
}
}

int solve(int a, int *b, int n) {
int N = 1;
while (N <= 2 * n)
N <<= 1;
ntt(a, N, 1);
ntt(b, N, 1);
for (int i = 0; i < N; ++i)
a[i] = 1LL * a[i] * b[i] % MOD;
ntt(a, N, -1);
return a;
}

int main() {
int a[16] = {1, 2, 1};
int b[16] = {3, 4, 1};
solve(a, b, 2);
for (int i = 0; i < 16; ++i) {
printf(“%d\n”, a[i]);
}
// now a[] = {3, 10, 12, 6, 1};
}

python只要四行……充分说明了高级编程语言的方便之处 =。=
n = int(input())
for i in range(n):
a, b = map(int, input().split())
print(a * b)