ultmaster edited 6 年，8 月前
你可以用 FFT（快速傅里叶变换）在 $O(n \log n)$ 的时间内计算两个多项式的乘积。如果要模比较特殊的素数，例如 $998~244~353$，可以使用 NTT。具体实现细节不作要求，这里给出 API。
例如对两个 $n$ 阶多项式 $(a_0+a_1 x+a_2 x^2 + \cdots + a_n x^n)(b_0+b_1 x+b_2 x^2 + \cdots + b_n x^n)$ 的乘积，我们可以调用 solve 函数（请确保 a, b 数组足够大，因为展开结果可能更大，一般建议开到四倍以上）。
#include <bits/stdc++.h>
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};
}
// Routines for performing computations on dates. In these routines,
// months are exprsesed as integers from 1 to 12, days are expressed
// as integers from 1 to 31, and years are expressed as 4-digit
// integers.
string dayOfWeek[] = {"Mo", "Tu", "We", "Th", "Fr", "Sa", "Su"};
// converts Gregorian date to integer (Julian day number)
int DateToInt (int m, int d, int y){
return
1461 * (y + 4800 + (m - 14) / 12) / 4 +
367 * (m - 2 - (m - 14) / 12 * 12) / 12 -
3 * ((y + 4900 + (m - 14) / 12) / 100) / 4 +
d - 32075;
}
// converts integer (Julian day number) to Gregorian date: month/day/year
void IntToDate (int jd, int &m, int &d, int &y){
int x, n, i, j;
x = jd + 68569;
n = 4 * x / 146097;
x -= (146097 * n + 3) / 4;
i = (4000 * (x + 1)) / 1461001;
x -= 1461 * i / 4 - 31;
j = 80 * x / 2447;
d = x - 2447 * j / 80;
x = j / 11;
m = j + 2 - 12 * x;
y = 100 * (n - 49) + i + x;
}
// converts integer (Julian day number) to day of week
string IntToDay (int jd){
return dayOfWeek[jd % 7];
}