畳み込み (lib/fft/ntt.hpp)

• View this file on GitHub
• Last update: 2025-11-18 14:07:26+09:00
• Include: #include "lib/fft/ntt.hpp"

Depends on

• lib/internal/internal_fft.hpp
• Montgomery modular multiplication (lib/internal/internal_math.hpp)
• lib/internal/internal_type_traits.hpp
• lib/math/modint.hpp
• lib/template/template.hpp

Required by

• 多倍長整数 (lib/data_structure/bigint.hpp)
• lib/fft/formal_power_series.hpp
• 任意mod畳み込み (lib/fft/ntt_mod.hpp)
• lib/math/bell.hpp
• Bostan-Mori法 (lib/math/bostan_mori.hpp)

Verified with

• test/aoj/ntl/addition.test.cpp
• test/aoj/ntl/difference.test.cpp
• test/aoj/ntl/division.test.cpp
• test/aoj/ntl/multiplication.test.cpp
• test/aoj/ntl/multiplication2.test.cpp
• test/aoj/ntl/remainder.test.cpp
• test/yosupo/convolution/convolution.test.cpp
• test/yosupo/convolution/convolution_mod.test.cpp
• test/yosupo/data_structure/addition_of_big_integers.test.cpp
• test/yosupo/enumerative_conbinatorics/bell_number.test.cpp
• test/yosupo/math/bostan_mori.test.cpp
• test/yosupo/polynomial/division_of_polynomials.test.cpp
• test/yosupo/polynomial/exp_of_formal_power_series.test.cpp
• test/yosupo/polynomial/inv_of_formal_power_series.test.cpp
• test/yosupo/polynomial/log_of_formal_power_series.test.cpp
• test/yosupo/polynomial/multipoint_evaluation.test.cpp
• test/yosupo/polynomial/polynomial_interpolation.test.cpp
• test/yosupo/polynomial/polynomial_taylor_shift.test.cpp
• test/yosupo/polynomial/pow_of_formal_power_series.test.cpp
• test/yosupo/polynomial/product_of_polynomial_sequence.test.cpp

Code

#pragma once
#include <algorithm>
#include <bit>
#include <cassert>
#include <type_traits>
#include <vector>
#include "internal/internal_fft.hpp"
#include "template/template.hpp"

/**
 * @brief 畳み込み
 *
 * @tparam mint
 * @param a
 * @param b
 * @return std::vector<mint>
 */
template <class mint, internal::is_static_modint_t<mint> * = nullptr>
std::vector<mint> convolution(std::vector<mint> &&a, std::vector<mint> &&b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};

    int z = std::bit_ceil<unsigned>(n + m - 1);
    assert((mint::mod() - 1) % z == 0);

    if (std::min(n, m) <= 60) return convolution_naive(a, b);
    return internal::convolution_fft(a, b);
}
template <class mint, internal::is_static_modint_t<mint> * = nullptr>
std::vector<mint> convolution(const std::vector<mint> &a, const std::vector<mint> &b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};

    int z = std::bit_ceil<unsigned>(n + m - 1);
    assert((mint::mod() - 1) % z == 0);

    if (std::min(n, m) <= 60) return convolution_naive(a, b);
    return internal::convolution_fft(a, b);
}

template <unsigned int mod = 998244353, class T, std::enable_if_t<std::is_integral<T>::value> * = nullptr>
std::vector<T> convolution(const std::vector<T> &a, const std::vector<T> &b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};

    using mint = static_modint<mod>;

    int z = std::bit_ceil<unsigned>(n + m - 1);
    assert((mint::mod() - 1) % z == 0);

    std::vector<mint> a2(n), b2(m);
    for (int i = 0; i < n; i++) { a2[i] = mint(a[i]); }
    for (int i = 0; i < m; i++) { b2[i] = mint(b[i]); }
    auto c2 = convolution(std::move(a2), std::move(b2));
    std::vector<T> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) { c[i] = c2[i].val(); }
    return c;
}

std::vector<std::int64_t> convolution_ll(const std::vector<std::int64_t> &a, const std::vector<std::int64_t> &b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};

    static constexpr std::uint64_t MOD1 = 754974721;  // 2^24
    static constexpr std::uint64_t MOD2 = 167772161;  // 2^25
    static constexpr std::uint64_t MOD3 = 469762049;  // 2^26
    static constexpr std::uint64_t M2M3 = MOD2 * MOD3;
    static constexpr std::uint64_t M1M3 = MOD1 * MOD3;
    static constexpr std::uint64_t M1M2 = MOD1 * MOD2;
    static constexpr std::uint64_t M1M2M3 = MOD1 * MOD2 * MOD3;

    static constexpr std::uint64_t i1 = internal::inv_gcd(MOD2 * MOD3, MOD1).second;
    static constexpr std::uint64_t i2 = internal::inv_gcd(MOD1 * MOD3, MOD2).second;
    static constexpr std::uint64_t i3 = internal::inv_gcd(MOD1 * MOD2, MOD3).second;

    static constexpr int MAX_AB_BIT = 24;
    static_assert(MOD1 % (1ull << MAX_AB_BIT) == 1, "MOD1 isn't enough to support an array length of 2^24.");
    static_assert(MOD2 % (1ull << MAX_AB_BIT) == 1, "MOD2 isn't enough to support an array length of 2^24.");
    static_assert(MOD3 % (1ull << MAX_AB_BIT) == 1, "MOD3 isn't enough to support an array length of 2^24.");
    assert(n + m - 1 <= (1 << MAX_AB_BIT));

    auto c1 = convolution<MOD1>(a, b);
    auto c2 = convolution<MOD2>(a, b);
    auto c3 = convolution<MOD3>(a, b);

    std::vector<std::int64_t> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) {
        std::uint64_t x = 0;
        x += (c1[i] * i1) % MOD1 * M2M3;
        x += (c2[i] * i2) % MOD2 * M1M3;
        x += (c3[i] * i3) % MOD3 * M1M2;
        std::int64_t diff = c1[i] - internal::safe_mod((std::int64_t)(x), (std::int64_t)(MOD1));
        if (diff < 0) diff += MOD1;
        static constexpr std::uint64_t offset[5] = {0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
        x -= offset[diff % 5];
        c[i] = x;
    }

    return c;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: internal/internal_fft.hpp: line -1: no such header

Back to top page