standalone_test/convolution/convolution_mod.fft_dfs_order_iteration.test.cpp

• View this file on GitHub
• Last update: 2026-04-26 11:16:42+08:00
• Problem: https://judge.yosupo.jp/problem/convolution_mod

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/convolution_mod

#include <cassert>
#include <cstring>
#include <iostream>
#include <utility>
#include <vector>

using uint         = unsigned;
using ull          = unsigned long long;
constexpr uint MOD = 998244353;

constexpr uint PowMod(uint a, ull e) {
    for (uint res = 1;; a = (ull)a * a % MOD) {
        if (e & 1) res = (ull)res * a % MOD;
        if ((e /= 2) == 0) return res;
    }
}

constexpr uint InvMod(uint a) { return PowMod(a, MOD - 2); }

constexpr uint QUAD_NONRESIDUE = 3;
constexpr int LOG2_ORD         = __builtin_ctz(MOD - 1);
constexpr uint ZETA            = PowMod(QUAD_NONRESIDUE, (MOD - 1) >> LOG2_ORD);
constexpr uint INV_ZETA        = InvMod(ZETA);

std::pair<std::vector<uint>, std::vector<uint>> GetFFTRoot(int n) {
    assert((n & (n - 1)) == 0);
    if (n / 2 == 0) return {};
    std::vector<uint> root(n / 2), inv_root(n / 2);
    root[0] = inv_root[0] = 1;
    for (int i = 0; (1 << i) < n / 2; ++i)
        root[1 << i]               = PowMod(ZETA, 1LL << (LOG2_ORD - i - 2)),
                  inv_root[1 << i] = PowMod(INV_ZETA, 1LL << (LOG2_ORD - i - 2));
    for (int i = 1; i < n / 2; ++i)
        root[i]     = (ull)root[i - (i & (i - 1))] * root[i & (i - 1)] % MOD,
        inv_root[i] = (ull)inv_root[i - (i & (i - 1))] * inv_root[i & (i - 1)] % MOD;
    return {root, inv_root};
}

int GetFFTSize(int n) {
    int len = 1;
    while (len < n) len *= 2;
    return len;
}

void FFT(uint a[], int n, const uint root[]) {
    for (int L = __builtin_ctz(n), C = 0; n > 1;) {
        uint *const b = a + (C << L);
        for (int i = 0, N = 1 << (L - 1); i < N; ++i) {
            const uint u = b[i];
            if (C) b[i + N] = (ull)b[i + N] * root[C] % MOD;
            if ((b[i] += b[i + N]) >= MOD) b[i] -= MOD;
            if ((b[i + N] = u + MOD - b[i + N]) >= MOD) b[i + N] -= MOD;
        }
        if (C == n / 2 - 1) break;
        if (L != 1) --L, C *= 2;
        else { L += __builtin_ctz(C + 1), C = (C >> __builtin_ctz(C + 1)) + 1; }
    }
}

void InvFFT(uint a[], int n, const uint root[]) {
    for (int L = 1, C = 0; n > 1;) {
        uint *const b = a + (C << L);
        for (int i = 0, N = 1 << (L - 1); i < N; ++i) {
            const uint u = b[i];
            if ((b[i] += b[i + N]) >= MOD) b[i] -= MOD;
            if (C) b[i + N] = (ull)(u + MOD - b[i + N]) * root[C] % MOD;
            else if ((b[i + N] = u + MOD - b[i + N]) >= MOD) { b[i + N] -= MOD; }
        }
        if (L == __builtin_ctz(n)) break;
        if (C & 1) ++L, C /= 2;
        else { C = (C << (L - 1) | ((1 << (L - 1)) - 1)) + 1, L = 1; }
    }
    const uint invN = InvMod(n);
    for (int i = 0; i < n; ++i) a[i] = (ull)a[i] * invN % MOD;
}

std::vector<uint> Product(std::vector<uint> a, std::vector<uint> b) {
    if (empty(a) || empty(b)) return {};
    const int n = size(a), m = size(b);
    const int N                 = GetFFTSize(n + m - 1);
    const auto [root, inv_root] = GetFFTRoot(N);
    a.resize(N), b.resize(N);
    FFT(data(a), N, data(root)), FFT(data(b), N, data(root));
    for (int i = 0; i < N; ++i) a[i] = (ull)a[i] * b[i] % MOD;
    InvFFT(data(a), N, data(inv_root));
    a.resize(n + m - 1);
    return a;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m;
    std::cin >> n >> m;
    std::vector<uint> a(n), b(m);
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    for (int i = 0; i < m; ++i) std::cin >> b[i];
    const auto ab = Product(std::move(a), std::move(b));
    for (int i = 0; i < n + m - 1; ++i) std::cout << ab[i] << ' ';
    return 0;
}

#line 1 "standalone_test/convolution/convolution_mod.fft_dfs_order_iteration.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/convolution_mod

#include <cassert>
#include <cstring>
#include <iostream>
#include <utility>
#include <vector>

using uint         = unsigned;
using ull          = unsigned long long;
constexpr uint MOD = 998244353;

constexpr uint PowMod(uint a, ull e) {
    for (uint res = 1;; a = (ull)a * a % MOD) {
        if (e & 1) res = (ull)res * a % MOD;
        if ((e /= 2) == 0) return res;
    }
}

constexpr uint InvMod(uint a) { return PowMod(a, MOD - 2); }

constexpr uint QUAD_NONRESIDUE = 3;
constexpr int LOG2_ORD         = __builtin_ctz(MOD - 1);
constexpr uint ZETA            = PowMod(QUAD_NONRESIDUE, (MOD - 1) >> LOG2_ORD);
constexpr uint INV_ZETA        = InvMod(ZETA);

std::pair<std::vector<uint>, std::vector<uint>> GetFFTRoot(int n) {
    assert((n & (n - 1)) == 0);
    if (n / 2 == 0) return {};
    std::vector<uint> root(n / 2), inv_root(n / 2);
    root[0] = inv_root[0] = 1;
    for (int i = 0; (1 << i) < n / 2; ++i)
        root[1 << i]               = PowMod(ZETA, 1LL << (LOG2_ORD - i - 2)),
                  inv_root[1 << i] = PowMod(INV_ZETA, 1LL << (LOG2_ORD - i - 2));
    for (int i = 1; i < n / 2; ++i)
        root[i]     = (ull)root[i - (i & (i - 1))] * root[i & (i - 1)] % MOD,
        inv_root[i] = (ull)inv_root[i - (i & (i - 1))] * inv_root[i & (i - 1)] % MOD;
    return {root, inv_root};
}

int GetFFTSize(int n) {
    int len = 1;
    while (len < n) len *= 2;
    return len;
}

void FFT(uint a[], int n, const uint root[]) {
    for (int L = __builtin_ctz(n), C = 0; n > 1;) {
        uint *const b = a + (C << L);
        for (int i = 0, N = 1 << (L - 1); i < N; ++i) {
            const uint u = b[i];
            if (C) b[i + N] = (ull)b[i + N] * root[C] % MOD;
            if ((b[i] += b[i + N]) >= MOD) b[i] -= MOD;
            if ((b[i + N] = u + MOD - b[i + N]) >= MOD) b[i + N] -= MOD;
        }
        if (C == n / 2 - 1) break;
        if (L != 1) --L, C *= 2;
        else { L += __builtin_ctz(C + 1), C = (C >> __builtin_ctz(C + 1)) + 1; }
    }
}

void InvFFT(uint a[], int n, const uint root[]) {
    for (int L = 1, C = 0; n > 1;) {
        uint *const b = a + (C << L);
        for (int i = 0, N = 1 << (L - 1); i < N; ++i) {
            const uint u = b[i];
            if ((b[i] += b[i + N]) >= MOD) b[i] -= MOD;
            if (C) b[i + N] = (ull)(u + MOD - b[i + N]) * root[C] % MOD;
            else if ((b[i + N] = u + MOD - b[i + N]) >= MOD) { b[i + N] -= MOD; }
        }
        if (L == __builtin_ctz(n)) break;
        if (C & 1) ++L, C /= 2;
        else { C = (C << (L - 1) | ((1 << (L - 1)) - 1)) + 1, L = 1; }
    }
    const uint invN = InvMod(n);
    for (int i = 0; i < n; ++i) a[i] = (ull)a[i] * invN % MOD;
}

std::vector<uint> Product(std::vector<uint> a, std::vector<uint> b) {
    if (empty(a) || empty(b)) return {};
    const int n = size(a), m = size(b);
    const int N                 = GetFFTSize(n + m - 1);
    const auto [root, inv_root] = GetFFTRoot(N);
    a.resize(N), b.resize(N);
    FFT(data(a), N, data(root)), FFT(data(b), N, data(root));
    for (int i = 0; i < N; ++i) a[i] = (ull)a[i] * b[i] % MOD;
    InvFFT(data(a), N, data(inv_root));
    a.resize(n + m - 1);
    return a;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m;
    std::cin >> n >> m;
    std::vector<uint> a(n), b(m);
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    for (int i = 0; i < m; ++i) std::cin >> b[i];
    const auto ab = Product(std::move(a), std::move(b));
    for (int i = 0; i < n + m - 1; ++i) std::cout << ab[i] << ' ';
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
clang++	all_same_00	AC	427 ms	45 MB
clang++	all_same_01	AC	458 ms	43 MB
clang++	all_same_02	AC	471 ms	43 MB
clang++	all_same_03	AC	458 ms	43 MB
clang++	example_00	AC	9 ms	22 MB
clang++	example_01	AC	9 ms	22 MB
clang++	fft_killer_00	AC	643 ms	43 MB
clang++	fft_killer_01	AC	639 ms	43 MB
clang++	fft_killer_02	AC	631 ms	41 MB
clang++	fft_killer_03	AC	630 ms	45 MB
clang++	fft_killer_04	AC	631 ms	43 MB
clang++	fft_killer_05	AC	630 ms	43 MB
clang++	fft_killer_06	AC	641 ms	43 MB
clang++	fft_killer_07	AC	636 ms	45 MB
clang++	fft_killer_08	AC	641 ms	41 MB
clang++	fft_killer_09	AC	626 ms	41 MB
clang++	max_ans_zero_00	AC	656 ms	45 MB
clang++	max_random_00	AC	645 ms	43 MB
clang++	max_random_01	AC	640 ms	43 MB
clang++	medium_00	AC	16 ms	24 MB
clang++	medium_01	AC	12 ms	20 MB
clang++	medium_02	AC	15 ms	20 MB
clang++	medium_all_zero_00	AC	13 ms	24 MB
clang++	medium_pre_suf_zero_00	AC	9 ms	20 MB
clang++	medium_pre_suf_zero_01	AC	9 ms	24 MB
clang++	medium_pre_suf_zero_02	AC	8 ms	18 MB
clang++	medium_pre_suf_zero_03	AC	9 ms	20 MB
clang++	medium_pre_suf_zero_04	AC	9 ms	24 MB
clang++	random_00	AC	650 ms	44 MB
clang++	random_01	AC	629 ms	44 MB
clang++	random_02	AC	299 ms	33 MB
clang++	signed_overflow_00	AC	9 ms	24 MB
clang++	small_00	AC	9 ms	20 MB
clang++	small_01	AC	9 ms	22 MB
clang++	small_02	AC	9 ms	24 MB
clang++	small_03	AC	9 ms	20 MB
clang++	small_04	AC	9 ms	22 MB
clang++	small_05	AC	9 ms	22 MB
clang++	small_06	AC	9 ms	24 MB
clang++	small_07	AC	9 ms	20 MB
clang++	small_08	AC	9 ms	18 MB
clang++	small_09	AC	9 ms	18 MB
clang++	small_10	AC	9 ms	20 MB
clang++	small_11	AC	9 ms	24 MB
clang++	small_12	AC	8 ms	24 MB
clang++	small_13	AC	8 ms	21 MB
clang++	small_14	AC	8 ms	22 MB
clang++	small_15	AC	8 ms	20 MB
clang++	small_and_large_00	AC	530 ms	41 MB
clang++	small_and_large_01	AC	545 ms	43 MB
clang++	small_and_large_02	AC	529 ms	40 MB
clang++	small_and_large_03	AC	541 ms	41 MB
clang++	unsigned_overflow_00	AC	9 ms	22 MB

Back to top page