3 条题解
-
1
更好的阅读体验：https://blog.csdn.net/tenkuo/article/details/150500190
诱导公式： https://blog.csdn.net/tenkuo/article/details/153632690
// a 数组一开始存的是系数，后面通过 a1 和 a2 计算得出每一个 k 对应的 y 值 // limit：数组的大小，*a 当前数组 void FFT(int limit, complex *a) { if(limit == 1) return; // 递归终止条件：只有一个常数项 //最后 n = 1的情况只有一个常数 a0，本来 a数组里面就存着，啥也不干直接返回就好 complex a1[limit>>1], a2[limit>>1]; // 按下标奇偶性分类 for(int i = 0; i < limit; i += 2) { a1[i>>1] = a[i]; // 偶数下标 a2[i>>1] = a[i+1]; // 奇数下标 } // 递归处理两个子问题 FFT(limit >> 1, a1); FFT(limit >> 1, a2); // 计算单位根 complex Wn = complex( cos(2.0 * Pi / limit), sin(2.0 * Pi / limit) ); //pi 就是圆周率 π，在完整代码中会讲怎么定义，Wn 是一开始先计算的 w_n^1 complex w = complex( 1, 0 ); // 当前的 w_n^k // 此时 w 还只是一个乘积基底，也就是 1，所以等于 1 + 0*i // 合并结果，计算每一个 w_n^k的 y for(int i = 0; i < (limit>>1); i++, w = w * Wn) { //蝴蝶操作（代码后面有解释为啥叫这个） complex t = w * a2[i]; //因为 w * a2[i]计算了两次，设个变量能省点时间 a[i] = a1[i] + t; a[i + (limit>>1)] = a1[i] - t; } }
https://www.luogu.com.cn/problem/P3803#include<bits/stdc++.h> using namespace std; const int N = 3e6 + 10; //这里得开大点，最好是 2 * (maxn + maxm) const double Pi = acos(-1.0); // acos(-1.0)是 π 的精确值（自行百度） struct Complex { // 我这里自定义复数结构体啦，c++库里也有 double x, y; // x为实部，y为虚部 } a[N], b[N]; // 两个多项式的数组 Complex operator+(Complex a, Complex b) { //重载复数加法 return {a.x + b.x, a.y + b.y}; } Complex operator-(Complex a, Complex b) { //重载复数减法 return {a.x - b.x, a.y - b.y}; } Complex operator*(Complex a, Complex b) { return {a.x * b.x - a.y * b.y , a.x * b.y + a.y * b.x}; // 重载复数乘法 (a+bi) * (c+di) = (ac-bd) + (ad+bc)i } int n, m, l, r[N]; // r是位逆序 int limit; // FFT变换长度 void FFT(Complex *A, int type) { //type：1表示正变换，-1表示逆变换，后面有解释 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是当前子问题的半长 //Wn = cos( 2 * Pi / limit ) + i * type * sin( 2 * Pi / limit ) //关于逆变换的 w_n^{-k}，就等于 w_n^{n - k}，sin值要变成负的，直接乘是 -1的 type就好 Complex Wn = { cos(Pi / mid), type * sin(Pi / mid) }; // R是当前子问题的完整长度，j表示当前处理到哪个位置 for(int R = mid << 1, j = 0; j < limit; j += R) { Complex w = {1, 0}; // 枚举子问题的左半部分（0到mid-1） for(int k = 0; k < mid; k++, w = w * Wn) { // 蝴蝶操作 // 这里可以把 j + k 当作 i，x 当作 a1[i]，y 当作 a2[i] Complex x = A[j + k]; Complex y = w * A[j + mid + k]; A[j + k] = x + y; A[j + mid + k] = x - y; } } } } 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].x; // 实部为系数，虚部默认为 0 a[i].y = 0; } for(int i = 0; i <= m; i++) { cin >> b[i].x; b[i].y = 0; } limit = 1; l = 0; // 是这个意思 limit < n + m + 1 while (limit <= n + m) { // 实际运用中并不严格要求 n 和 m 都是形如 2^k 的数 // 我们会计算出 >= n + m + 1 最小的二进制数 limit，用 limit 来 FFT // 相当于将多出来的位补 0 limit <<= 1; l++; } for (int i = 0; i < limit; i++) { // 计算二进制位逆序 r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1)); //i>>1：去掉 i 的最低位，r[i>>1]：得到 i>>1 的位逆序 //r[i>>1]>>1：将位逆序右移一位（为新位腾出空间） //i&1：获取 i 的最低位，(i&1)<<(l-1)：将最低位移到最高位 //最后合并两部分 //自己试一下验证正确性 // 因为 i >> 1 后，前面肯定会空出一个该有的位 // 所以 r[i >> 1] 的最后一个位是 0 // 这个 0 本来是属于 i 的最低位的，现在移走让最低位到最前面 } // FFT正变换 FFT(a, 1); FFT(b, 1); for (int i = 0; i < limit; i++) { a[i] = a[i] * b[i]; //两两点值相乘 } // FFT逆变换 FFT(a, -1); for(int i = 0; i <= n + m; i++) { cout << (int)(a[i].x / limit + 0.5) << " "; //逆变换后需要除以 limit // 为什么要 + 0.5 四舍五入，理论上应该得到整数 42 // 但由于 fft 浮点误差，实际可能是： // 42.0000000001 或 41.9999999999 } cout << "\n"; return 0; }
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int M = 3e6 + 10; //这里得开大点，最好是 2 * (maxn + maxm) 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++; } 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); LL invl = qpow(limit, P - 2); //计算 N在模 P下的逆元 for (int i = 0; i < n + m + 1; i++) { cout << a[i] * invl % P << " "; // 逆变换后需要除以 limit（乘以 limit的逆元） } cout << endl; return 0; }update 2025.12.7：修正了原文表达模糊的部分，添加了更细致的公式推导。
update 2025.12.14：重写了 6.FFT 逆变换 和 7.FFT 的正确性证明。
update 2026.8.2：修正了定义域错误，添加代码注释。
-
0
#include<bits/stdc++.h> using namespace std; #define int long long const int N=2e6+10,P=998244353; int qpow(int a,int b){int ans=1;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;} int a[N],b[N],c[N]; void ntt(int s[],int n,int x) { if(n==1)return; int s1[n/2],s2[n/2]; for(int i=0;i<n/2;i++)s1[i]=s[2*i],s2[i]=s[2*i+1]; ntt(s1,n/2,x*x%P);ntt(s2,n/2,x*x%P); for(int i=0,xi=1;i<n/2;i++,xi=xi*x%P) { s[i]=(s1[i]+s2[i]*xi)%P; s[i+n/2]=((s1[i]-s2[i]*xi)%P+P)%P; } } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,m;cin>>n>>m; for(int i=0;i<n;i++)cin>>a[i]; for(int i=0;i<m;i++)cin>>b[i]; int D=1;while(D<n+m-1)D<<=1;int inv=qpow(D,P-2); int x=qpow(3,(P-1)/D); ntt(a,D,x);ntt(b,D,x); for(int i=0;i<D;i++)c[i]=a[i]*b[i]%P; int inv1=qpow(x,P-2); ntt(c,D,inv1); for(int i=0;i<n+m-1;i++)cout<<c[i]*inv%P<<' '; return 0; } -
0
卷积定义题目里已经说的很明确了，先打个暴力试试水：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1 << 20; const LL P = 998244353; LL a[N], b[N], ans[N]; template<typename T> void qr(T &x) { int f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') { f = -1; } for (; isdigit(c); c = getchar()) { x = x * 10 + (c - '0'); } x *= f; } template<typename T> void qw(T x) { if (x < 0) { putchar('-'); x *= -1; } if (x >= 10) { qw(x / 10); } putchar(x % 10 + '0'); } int main () { ios::sync_with_stdio(false); cin.tie(0); int n, m; qr(n); qr(m); for (int i = 0; i < n; i ++) { qr(a[i]); } for (int i = 0; i < m; i ++) { qr(b[i]); } for (int i = 0; i < n; i ++) { for (int j = 0; j < m; j ++) { ans[i + j]= (ans[i + j] + a[i] * b[j] % P) % P; } } for (int i = 0; i <= n - 1 + m - 1; i ++) { qw(ans[i]); putchar(' '); } putchar('\n'); return 0; }因为时间复杂度的大头是 N^2 枚举，所以快读不能起什么作用，加与不加都是 64 分。
考虑到数据范围是 10^6，又是大整数计算，可以使用 NTT。 没学过指路：https://blog.csdn.net/tenkuo/article/details/150500190
直接套板子即可：
#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; }另：本题是卡 FFT 的，甚至只能拿到 4 分（大数据下 FFT 会有精度问题）。 椰树神了喵。
- 1
