多项式
- 形式化的，一个多项式 (f(x)) 可以表示为
[f(x)=sum _ia_ix^i
]
多项式加减法
- 直接对应系数相加减
多项式乘法
- 可以解决形如 (Q_j=sum_{i=0}^{j}f_ig_{j-i}) 的卷积
快速傅里叶变换(FFT)
-
前置知识：离散傅里叶变换(DFT)、复数、单位根
-
用DFT将系数表达式转换为点值表达式，运算后再用IDFT转换为系数表达式
Show Code
#include <cmath>
#include <cstdio>
#define swap(x, y) ({Complex xx = x; x = y; y = xx;})
#define Mul(x, y) ((Complex) {x.r * y.r - x.i * y.i, x.r * y.i + x.i * y.r})
const double pi = acos(-1);
const int N = (1 << 18) + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
struct Complex {
double r, i;
}a[N], b[N];
int n, m, l, k, r[N];
void FFT(Complex *a, int k) {
for (int i = 0; i <= l; ++i)
if (i < r[i]) swap(a[i], a[r[i]]);
for (int d = 1; d < l; d *= 2) {
int d2 = d * 2;
Complex W = (Complex) {cos(pi / d), sin(pi / d) * k};
for (int i = 0; i < l; i += d2) {
Complex w = (Complex) {1, 0};
for (int j = i; j < i + d; ++j, w = Mul(w, W)) {
Complex x = a[j], y = Mul(a[j+d], w);
a[j] = (Complex) {x.r + y.r, x.i + y.i};
a[j+d] = (Complex) {x.r - y.r, x.i - y.i};
}
}
}
}
int main() {
n = read(); m = read();
for (int i = 0; i <= n; ++i)
a[i].r = read();
for (int i = 0; i <= m; ++i)
b[i].r = read();
for (l = 1; l <= n + m; l *= 2, ++k); --k;
for (int i = 0; i < l; ++i)
r[i] = (r[i>>1] >> 1) | ((i & 1) << k);
FFT(a, 1); FFT(b, 1);
for (int i = 0; i < l; ++i)
a[i] = Mul(a[i], b[i]);
FFT(a, -1);
for (int i = 0; i <= n + m; ++i)
printf("%d ", (int)(a[i].r / l + 0.5));
return 0;
}
快速数论变换(NTT) (最新)
- NTT可以解决有模数的问题，结果更加准确，用原根替代单位根，预处理单位根会快很多
Show Code
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 1 << 18 | 5, M = 998244353;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int n, m, a[N], b[N], r[N], w[N], l, k;
int Pow(int a, int k, int ans = 1) {
for (; k; k >>= 1, a = 1ll * a * a % M)
if (k & 1) ans = 1ll * ans * a % M;
return ans;
}
void NTT(int *a, bool g = 1) {
for (int i = 0; i < l; ++i)
if (i < r[i]) std::swap(a[i], a[r[i]]);
for (int m = 1, d = 2; m < l; m *= 2, d *= 2) {
for (int i = 0; i < l; i += d) {
for (int j = i; j < i + m; ++j) {
int x = a[j], y = 1ll * a[j+m] * w[m+j-i] % M;
if ((a[j] = x + y) >= M) a[j] -= M;
if ((a[j+m] = x - y) < 0) a[j+m] += M;
}
}
}
if (!g) std::reverse(a + 1, a + l);
}
int main() {
n = read(); m = read();
for (int i = 0; i <= n; ++i) a[i] = read();
for (int i = 0; i <= m; ++i) b[i] = read();
for (l = 1; l < n + m; l *= 2); k = l >> 1;
w[k] = 1; w[k+1] = Pow(3, (M - 1) / l);
for (int i = k + 2; i < l; ++i) w[i] = 1ll * w[i-1] * w[k+1] % M;
for (int i = k - 1; i >= 0; --i) w[i] = w[i*2];
for (int i = 0; i < l; ++i) r[i] = (r[i>>1] >> 1) | (i & 1 ? k : 0);
NTT(a); NTT(b);
for (int i = 0; i < l; ++i) a[i] = 1ll * a[i] * b[i] % M;
NTT(a, 0);
int inv = Pow(l, M - 2);
for (int i = 0; i <= n + m; ++i) printf("%lld ", 1ll * a[i] * inv % M);
return 0;
}
快速沃尔什变换(FWT)
[C_i=sum _{i=jigoplus k}A_iB_j
]
- 有的卷积形式中 (igoplus) 可能不是+，而是位运算，这就需要FWT了
Show Code
#include <cstdio>
#include <cstring>
const int N = 1 << 17 | 5, M = 998244353, inv2 = 499122177;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int n, A[N], B[N], a[N], b[N];
void FWT(int *a, int od, bool g = 0) {
for (int d = 1; d < n; d *= 2) {
for (int i = 0, d2 = d * 2; i < n; i += d2) {
for (int j = i; j < i + d; ++j) {
if (od == 1) {// or 或 |
if (!g && (a[j+d] += a[j]) >= M) a[j+d] -= M;
else if (g && (a[j+d] -= a[j]) < 0) a[j+d] += M;
}
else if (od == 2) {// ans 与 &
if (!g && (a[j] += a[j+d]) >= M) a[j] -= M;
else if (g && (a[j] -= a[j+d]) < 0) a[j] += M;
}
else { // xor 异或 ^
int x = a[j], y = a[j+d];
if ((a[j] = x + y) >= M) a[j] -= M;
if ((a[j+d] = x - y) < 0) a[j+d] += M;
if (g) a[j] = 1ll * a[j] * inv2 % M, a[j+d] = 1ll * a[j+d] * inv2 % M;
}
}
}
}
}
void Solve(int k) {
memcpy(a, A, n * 4);
memcpy(b, B, n * 4);
FWT(a, k); FWT(b, k);
for (int i = 0; i < n; ++i)
a[i] = 1ll * a[i] * b[i] % M;
FWT(a, k, 1);
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
puts("");
}
int main() {
n = 1 << read();
for (int i = 0; i < n; ++i)
A[i] = read();
for (int i = 0; i < n; ++i)
B[i] = read();
Solve(1); Solve(2); Solve(3);
return 0;
}