Star's Blog

1
#include <iostream>
2
#include <cmath>
3

4
using namespace std;
5

6
const int N = 300000;
7
const double PI = acos(-1);
8
struct Complex {
9
    double x, y;
10

11
    Complex operator +(const Complex &t) const {
12
        return {x + t.x, y + t.y};
13
    }
14

15
    Complex operator -(const Complex &t) const {
16
        return {x - t.x, y - t.y};
17
    }
18

19
    Complex operator *(const Complex &t) const {
20
        return {x * t.x - y * t.y, x * t.y + y * t.x};
21
    }
22
} a[N], b[N];
23
int rev[N], tot, bit;
24

25
void fft(Complex a[], int inv) {
26
    for (int i = 0; i < tot; ++i) {
27
        if (i < rev[i]) swap(a[i], a[rev[i]]);
28
    }
29
    for (int mid = 1; mid < tot; mid <<= 1) {
30
        Complex w1 = {cos(PI / mid), inv * sin(PI / mid)};
31
        for (int i = 0; i < tot; i += mid * 2) {
32
            Complex wk = {1, 0};
33
            for (int j = 0; j < mid; ++j, wk = wk * w1) {
34
                Complex x = a[i + j], y = wk * a[i + j + mid];
35
                a[i + j] = x + y, a[i + j + mid] = x - y;
36
            }
37
        }
38
    }
39
}
40

41
int main() {
42
    int n, m;
43
    scanf("%d%d", &n, &m);
44
    for (int i = 0; i <= n; ++i) scanf("%lf", &a[i].x);
45
    for (int i = 0; i <= m; ++i) scanf("%lf", &b[i].x);
46
    while ((1 << bit) < n + m + 1) bit++;
47
    tot = 1 << bit;
48
    for (int i = 0; i < tot; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
49
    fft(a, 1), fft(b, 1);
50
    for (int i = 0; i < tot; ++i) a[i] = a[i] * b[i];
51
    fft(a, -1);
52
    for (int i = 0; i < n + m + 1; ++i) {
53
        printf("%d ", int(a[i].x / tot + 0.5));
54
    }
55
    printf("\n");
56
    return 0;
57
}

1
#include <iostream>
2
#include <cstring>
3
#include <cmath>
4

5
using namespace std;
6
const int N = 300000;
7
const double PI = acos(-1);
8

9
struct Complex {
10
    double x, y;
11

12
    Complex operator +(const Complex &t) const {
13
        return {x + t.x, y + t.y};
14
    }
15

16
    Complex operator -(const Complex &t) const {
17
        return {x - t.x, y - t.y};
18
    }
19

20
    Complex operator *(const Complex &t) const {
21
        return {x * t.x - y * t.y, x * t.y + y * t.x};
22
    }
23
} a[N], b[N];
24
char s[N], t[N];
25
int rev[N], bit, tot;
26
int res[N];
27

28
void fft(Complex a[], int inv) {
29
    for (int i = 0; i < tot; ++i) {
30
        if (i < rev[i]) swap(a[i], a[rev[i]]);
31
    }
32
    for (int mid = 1; mid < tot; mid <<= 1) {
33
        Complex w1 = {cos(PI / mid), inv * sin(PI / mid)};
34
        for (int i = 0; i < tot; i += mid * 2) {
35
            Complex wk = {1, 0};
36
            for (int j = 0; j < mid; ++j, wk = wk * w1) {
37
                Complex x = a[i + j], y = wk * a[i + j + mid];
38
                a[i + j] = x + y, a[i + j + mid] = x - y;
39
            }
40
        }
41
    }
42
}
43

44
int main() {
45
    scanf("%s%s", s, t);
46
    int n = strlen(s) - 1, m = strlen(t) - 1;
47
    for (int i = 0; i <= n; ++i) a[i] = {double(s[n - i] - 48), 0};
48
    for (int i = 0; i <= m; ++i) b[i] = {double(t[m - i] - 48), 0};
49
    while ((1 << bit) < n + m + 1) bit++;
50
    tot = 1 << bit;
51
    for (int i = 0; i < tot; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
52
    fft(a, 1), fft(b, 1);
53
    for (int i = 0; i < tot; ++i) a[i] = a[i] * b[i];
54
    fft(a, -1);
55
    int len = 0;
56
    for (int i = 0; i <= n + m; ++i) {
57
        res[i] = int(a[i].x / tot + 0.5);
58
    }
59
    for (len = 0; len <= n + m || res[len]; ++len) {
60
        res[len + 1] += res[len] / 10, res[len] %= 10;
61
    }
62
    while (len > 1 && res[len - 1] == 0) len--;
63
    for (int i = len - 1; i >= 0; --i) putchar(res[i] + 48);
64
    putchar('\n');
65
    return 0;
66
}