【题解】LC：卷积（Convolution）（NTT）

板题。

考虑到数据范围是 10^6，又是大整数计算。

可以使用 NTT。 没学过指路：【FFT & NTT | 那忘算 7】快速傅里叶变换 & 快速数论变换 (洛谷 P3803 题解)_傅里叶 洛谷-CSDN博客

卡 fft 椰树神了喵。

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int M = 3e6 + 10; //这里得开大点，2e6 不够 const LL P = 998244353; LL qpow(LL a, LL b) { LL res = 1; a %= P; while (b) { if (b & 1) { res = res * a %P; } a = a * a %P; b /= 2; } return res; } LL a[M], b[M], r[M]; int limit, l; void NTT(LL *A, LL type) { //type：原根的特定幂次（正变换用原根，逆变换用原根的逆元） for (int i = 0; i < limit; i++) if(i < r[i]){ swap(A[i], A[r[i]]); } for (int mid = 1; mid < limit; mid <<= 1) { //mid 是当前半长 // 计算当前长度 2 * mid 对应的单位根：x ^ {limit / (2 * mid)} // 为什么是 limit / (2 * mid)？就相当于原来的 g^{(P - 1) / limit} 上面的幂次 *当前长度 /limit //就等于 g^{(P - 1) / 当前长度} LL Wn = qpow( type, limit / (2 * mid) ); // R是当前子问题的完整长度，j表示当前处理到哪个位置 for(int R = mid << 1, j = 0; j < limit; j += R) { LL w = 1; // 初始化当前单位根为 1（即 w_n^0） for(int k = 0; k < mid; k++, w = w * Wn %P) { // 蝴蝶操作 LL x = A[j + k]; LL y = w * A[j + mid + k] %P; A[j + k] = (x + y)%P; A[j + mid + k] = (x - y + P)%P; //这里一定要 + P！！不然会输出负数！！ } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n; cin >> m; for (int i = 0; i < n; i++) { cin >> a[i]; } for(int i = 0; i < m; i++) { cin >> b[i]; } limit = 1; l = 0; while (limit <= n + m) { limit <<= 1; l++; } LL invl = qpow(limit, P - 2); //计算 N在模 P下的逆元 for (int i = 0; i < limit; i++) { // 计算二进制位逆序 r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1)); } //(P-1)/N 是N次单位根 LL t = qpow(3ll, (P - 1) / limit); // 执行 NTT正变换 NTT(a, t); NTT(b, t); for (int i = 0; i <= limit; i++) { a[i] = a[i] * b[i] % P; } // 计算原根的逆元（用于逆变换） LL inv_t = qpow(t, P - 2); // 执行 NTT逆变换 NTT(a, inv_t); for (int i = 0; i <= n - 1 + m - 1; i++) { cout << a[i] * invl % P << " "; // 逆变换后需要除以 limit（乘以 limit的逆元） } cout << "\n"; return 0; }