【题解】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; }