0%

多项式

多项式相关的总结。

FFT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 3e6 + 5;
const double PI = acos(-1.0);

struct Complex
{
double x, y;
Complex(double x = 0, double y = 0) : x(x), y(y) {}
Complex operator + (const Complex &a) { return Complex(x + a.x, y + a.y); }
Complex operator - (const Complex &a) { return Complex(x - a.x, y - a.y); }
Complex operator * (const Complex &a) { return Complex(x * a.x - y * a.y, x * a.y + a.x * y); }
Complex operator / (double a) { return Complex(x / a, y / a); }
} f[N], g[N], h[N], tmp[N];

int n, m, rev[N];

void change(Complex y[], int len)
{
for (int i = 0; i < len; i++)
{
rev[i] = rev[i >> 1] >> 1;
if (i & 1) rev[i] |= len >> 1;
}
for (int i = 0; i < len; i++)
if (i < rev[i]) swap(y[i], y[rev[i]]);
}

void FFT(Complex y[], int len, int on)
{
change(y, len);
for (int h = 2; h <= len; h <<= 1)
{
Complex wn(cos(2 * PI / h), sin(on * 2 * PI / h));
for (int j = 0; j < len; j += h)
{
Complex w(1, 0);
for (int k = j; k < j + h / 2; k++)
{
Complex u = y[k];
Complex t = w * y[k + h / 2];
y[k] = u + t;
y[k + h / 2] = u - t;
w = w * wn;
}
}
}
if (on == -1)
for (int i = 0; i < len; i++) y[i].x /= len;
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++)
{
int x;
scanf("%d", &x);
f[i] = Complex(x, 0);
}
for (int i = 0; i <= m; i++)
{
int x;
scanf("%d", &x);
g[i] = Complex(x, 0);
}
int len = 1;
while (len <= n + m) len <<= 1;
FFT(f, len, 1);
FFT(g, len, 1);
for (int i = 0; i <= len; i++) h[i] = f[i] * g[i];
FFT(h, len, -1);
for (int i = 0; i <= n + m; i++) printf("%d ", (int)(h[i].x + 0.5));
return 0;
}

NTT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 3e6 + 5;
const int mod = 998244353;

int n, m, rev[N], f[N], g[N], h[N];

void change(int y[], int len)
{
for (int i = 0; i < len; i++)
{
rev[i] = rev[i >> 1] >> 1;
if (i & 1) rev[i] |= len >> 1;
}
for (int i = 0; i < len; i++)
if (i < rev[i]) swap(y[i], y[rev[i]]);
}

int qpow(int a, int b)
{
int res = 1;
for (; b; b >>= 1, a = 1LL * a * a % mod)
if (b & 1) res = 1LL * res * a % mod;
return res;
}

void NTT(int y[], int len, int on)
{
change(y, len);
for (int h = 2; h <= len; h <<= 1)
{
int gn = qpow(3, (mod - 1) / h);
for (int j = 0; j < len; j += h)
{
int g = 1;
for (int k = j; k < j + h / 2; k++)
{
int u = y[k];
int t = 1LL * g * y[k + h / 2] % mod;
y[k] = (u + t) % mod;
y[k + h / 2] = ((u - t) % mod + mod) % mod;
g = 1LL * g * gn % mod;
}
}
}
if (on == -1)
{
reverse(y + 1, y + len);
int inv = qpow(len, mod - 2);
for (int i = 0; i < len; i++) y[i] = 1LL * y[i] * inv % mod;
}
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++) scanf("%d", &f[i]);
for (int i = 0; i <= m; i++) scanf("%d", &g[i]);
int len = 1;
while (len <= n + m) len <<= 1;
NTT(f, len, 1);
NTT(g, len, 1);
for (int i = 0; i <= len; i++) h[i] = 1LL * f[i] * g[i] % mod;
NTT(h, len, -1);
for (int i = 0; i <= n + m; i++) printf("%d ", h[i]);
return 0;
}