hly1204's library
This documentation is automatically generated by online-judge-tools/verification-helper
test/convolution/convolution_mod_1000000007.0.test.cpp
- View this file on GitHub
- Last update: 2025-01-19 15:28:01+08:00
- Problem: https://judge.yosupo.jp/problem/convolution_mod_1000000007
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/convolution_mod_1000000007"
#include "conv_mod.hpp"
#include <iostream>
#include <vector>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<int> f(n), g(m);
for (int i = 0; i < n; ++i) std::cin >> f[i];
for (int i = 0; i < m; ++i) std::cin >> g[i];
const auto fg = convolution_mod(f, g, 1000000007);
for (int i = 0; i < (int)fg.size(); ++i) std::cout << fg[i] << ' ';
return 0;
}#line 1 "test/convolution/convolution_mod_1000000007.0.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/convolution_mod_1000000007"
#line 2 "conv_mod.hpp"
#line 2 "fft.hpp"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <memory>
#include <vector>
template<typename Tp> class FftInfo {
static Tp least_quadratic_nonresidue() {
for (int i = 2;; ++i)
if (Tp(i).pow((Tp::mod() - 1) / 2) == -1) return Tp(i);
}
const int ordlog2_;
const Tp zeta_;
const Tp invzeta_;
const Tp imag_;
const Tp invimag_;
mutable std::vector<Tp> root_;
mutable std::vector<Tp> invroot_;
FftInfo()
: ordlog2_(__builtin_ctzll(Tp::mod() - 1)),
zeta_(least_quadratic_nonresidue().pow((Tp::mod() - 1) >> ordlog2_)),
invzeta_(zeta_.inv()), imag_(zeta_.pow(1LL << (ordlog2_ - 2))), invimag_(-imag_),
root_{Tp(1), imag_}, invroot_{Tp(1), invimag_} {}
public:
static const FftInfo &get() {
static FftInfo info;
return info;
}
Tp imag() const { return imag_; }
Tp inv_imag() const { return invimag_; }
Tp zeta() const { return zeta_; }
Tp inv_zeta() const { return invzeta_; }
const std::vector<Tp> &root(int n) const {
// [0, n)
assert((n & (n - 1)) == 0);
if (const int s = root_.size(); s < n) {
root_.resize(n);
for (int i = __builtin_ctz(s); (1 << i) < n; ++i) {
const int j = 1 << i;
root_[j] = zeta_.pow(1LL << (ordlog2_ - i - 2));
for (int k = j + 1; k < j * 2; ++k) root_[k] = root_[k - j] * root_[j];
}
}
return root_;
}
const std::vector<Tp> &inv_root(int n) const {
// [0, n)
assert((n & (n - 1)) == 0);
if (const int s = invroot_.size(); s < n) {
invroot_.resize(n);
for (int i = __builtin_ctz(s); (1 << i) < n; ++i) {
const int j = 1 << i;
invroot_[j] = invzeta_.pow(1LL << (ordlog2_ - i - 2));
for (int k = j + 1; k < j * 2; ++k) invroot_[k] = invroot_[k - j] * invroot_[j];
}
}
return invroot_;
}
};
inline int fft_len(int n) {
--n;
n |= n >> 1, n |= n >> 2, n |= n >> 4, n |= n >> 8;
return (n | n >> 16) + 1;
}
namespace detail {
template<typename Iterator> inline void
butterfly_n(Iterator a, int n,
const std::vector<typename std::iterator_traits<Iterator>::value_type> &root) {
assert(n > 0);
assert((n & (n - 1)) == 0);
const int bn = __builtin_ctz(n);
if (bn & 1) {
for (int i = 0; i < n / 2; ++i) {
const auto a0 = a[i], a1 = a[i + n / 2];
a[i] = a0 + a1, a[i + n / 2] = a0 - a1;
}
}
for (int i = n >> (bn & 1); i >= 4; i /= 4) {
const int i4 = i / 4;
for (int k = 0; k < i4; ++k) {
const auto a0 = a[k + i4 * 0], a1 = a[k + i4 * 1];
const auto a2 = a[k + i4 * 2], a3 = a[k + i4 * 3];
const auto a02p = a0 + a2, a02m = a0 - a2;
const auto a13p = a1 + a3, a13m = (a1 - a3) * root[1];
a[k + i4 * 0] = a02p + a13p, a[k + i4 * 1] = a02p - a13p;
a[k + i4 * 2] = a02m + a13m, a[k + i4 * 3] = a02m - a13m;
}
for (int j = i, m = 2; j < n; j += i, m += 2) {
const auto r = root[m], r2 = r * r, r3 = r2 * r;
for (int k = j; k < j + i4; ++k) {
const auto a0 = a[k + i4 * 0], a1 = a[k + i4 * 1] * r;
const auto a2 = a[k + i4 * 2] * r2, a3 = a[k + i4 * 3] * r3;
const auto a02p = a0 + a2, a02m = a0 - a2;
const auto a13p = a1 + a3, a13m = (a1 - a3) * root[1];
a[k + i4 * 0] = a02p + a13p, a[k + i4 * 1] = a02p - a13p;
a[k + i4 * 2] = a02m + a13m, a[k + i4 * 3] = a02m - a13m;
}
}
}
}
template<typename Iterator> inline void
inv_butterfly_n(Iterator a, int n,
const std::vector<typename std::iterator_traits<Iterator>::value_type> &root) {
assert(n > 0);
assert((n & (n - 1)) == 0);
const int bn = __builtin_ctz(n);
for (int i = 4; i <= (n >> (bn & 1)); i *= 4) {
const int i4 = i / 4;
for (int k = 0; k < i4; ++k) {
const auto a0 = a[k + i4 * 0], a1 = a[k + i4 * 1];
const auto a2 = a[k + i4 * 2], a3 = a[k + i4 * 3];
const auto a01p = a0 + a1, a01m = a0 - a1;
const auto a23p = a2 + a3, a23m = (a2 - a3) * root[1];
a[k + i4 * 0] = a01p + a23p, a[k + i4 * 1] = a01m + a23m;
a[k + i4 * 2] = a01p - a23p, a[k + i4 * 3] = a01m - a23m;
}
for (int j = i, m = 2; j < n; j += i, m += 2) {
const auto r = root[m], r2 = r * r, r3 = r2 * r;
for (int k = j; k < j + i4; ++k) {
const auto a0 = a[k + i4 * 0], a1 = a[k + i4 * 1];
const auto a2 = a[k + i4 * 2], a3 = a[k + i4 * 3];
const auto a01p = a0 + a1, a01m = a0 - a1;
const auto a23p = a2 + a3, a23m = (a2 - a3) * root[1];
a[k + i4 * 0] = a01p + a23p, a[k + i4 * 1] = (a01m + a23m) * r;
a[k + i4 * 2] = (a01p - a23p) * r2, a[k + i4 * 3] = (a01m - a23m) * r3;
}
}
}
if (bn & 1) {
for (int i = 0; i < n / 2; ++i) {
const auto a0 = a[i], a1 = a[i + n / 2];
a[i] = a0 + a1, a[i + n / 2] = a0 - a1;
}
}
}
} // namespace detail
// FFT_n: A(x) |-> bit-reversed order of [A(1), A(zeta_n), ..., A(zeta_n^(n-1))]
template<typename Iterator> inline void fft_n(Iterator a, int n) {
using Tp = typename std::iterator_traits<Iterator>::value_type;
detail::butterfly_n(a, n, FftInfo<Tp>::get().root(n / 2));
}
template<typename Tp> inline void fft(std::vector<Tp> &a) { fft_n(a.begin(), a.size()); }
// IFFT_n: bit-reversed order of [A(1), A(zeta_n), ..., A(zeta_n^(n-1))] |-> A(x)
template<typename Iterator> inline void inv_fft_n(Iterator a, int n) {
using Tp = typename std::iterator_traits<Iterator>::value_type;
detail::inv_butterfly_n(a, n, FftInfo<Tp>::get().inv_root(n / 2));
const Tp iv = Tp::mod() - (Tp::mod() - 1) / n;
for (int i = 0; i < n; ++i) a[i] *= iv;
}
template<typename Tp> inline void inv_fft(std::vector<Tp> &a) { inv_fft_n(a.begin(), a.size()); }
// IFFT_n^T: A(x) |-> 1/n FFT_n((x^n A(x^(-1))) mod (x^n - 1))
template<typename Iterator> inline void transposed_inv_fft_n(Iterator a, int n) {
using Tp = typename std::iterator_traits<Iterator>::value_type;
const Tp iv = Tp::mod() - (Tp::mod() - 1) / n;
for (int i = 0; i < n; ++i) a[i] *= iv;
detail::butterfly_n(a, n, FftInfo<Tp>::get().inv_root(n / 2));
}
template<typename Tp> inline void transposed_inv_fft(std::vector<Tp> &a) {
transposed_inv_fft_n(a.begin(), a.size());
}
// FFT_n^T : FFT_n((x^n A(x^(-1))) mod (x^n - 1)) |-> n A(x)
template<typename Iterator> inline void transposed_fft_n(Iterator a, int n) {
using Tp = typename std::iterator_traits<Iterator>::value_type;
detail::inv_butterfly_n(a, n, FftInfo<Tp>::get().root(n / 2));
}
template<typename Tp> inline void transposed_fft(std::vector<Tp> &a) {
transposed_fft_n(a.begin(), a.size());
}
template<typename Tp> inline std::vector<Tp> convolution_fft(std::vector<Tp> a, std::vector<Tp> b) {
if (a.empty() || b.empty()) return {};
const int n = a.size();
const int m = b.size();
const int len = fft_len(n + m - 1);
a.resize(len);
b.resize(len);
fft(a);
fft(b);
for (int i = 0; i < len; ++i) a[i] *= b[i];
inv_fft(a);
a.resize(n + m - 1);
return a;
}
template<typename Tp> inline std::vector<Tp> square_fft(std::vector<Tp> a) {
if (a.empty()) return {};
const int n = a.size();
const int len = fft_len(n * 2 - 1);
a.resize(len);
fft(a);
for (int i = 0; i < len; ++i) a[i] *= a[i];
inv_fft(a);
a.resize(n * 2 - 1);
return a;
}
template<typename Tp>
inline std::vector<Tp> convolution_naive(const std::vector<Tp> &a, const std::vector<Tp> &b) {
if (a.empty() || b.empty()) return {};
const int n = a.size();
const int m = b.size();
std::vector<Tp> res(n + m - 1);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) res[i + j] += a[i] * b[j];
return res;
}
template<typename Tp>
inline std::vector<Tp> convolution(const std::vector<Tp> &a, const std::vector<Tp> &b) {
if (std::min(a.size(), b.size()) < 60) return convolution_naive(a, b);
if (std::addressof(a) == std::addressof(b)) return square_fft(a);
return convolution_fft(a, b);
}
#line 2 "modlong.hpp"
#include <iostream>
#include <type_traits>
template<unsigned long long Mod, bool Odd = (Mod & 1)> class ModLong;
// clang-format off
template<unsigned long long Mod> class ModLong<Mod, true> {
using LL = long long;
using ULL = unsigned long long;
static_assert((Mod >> 63) == 0, "`Mod` must less than 2^(63)");
static_assert((Mod & 1) == 1, "`Mod` must be odd");
template<typename Int> static std::enable_if_t<std::is_integral_v<Int>, ULL> safe_mod(Int v) { using D = std::common_type_t<Int, LL>; return (v %= (LL)Mod) < 0 ? (D)(v + (LL)Mod) : (D)v; }
static ULL norm(LL x) { return x < 0 ? x + (LL)Mod : x; }
static ULL norm(ULL x) { return x + (Mod & -(x >> 63)); }
struct PrivateConstructor {} static inline private_constructor;
ModLong(PrivateConstructor, ULL v) : v_(v) {}
ULL v_;
static constexpr ULL r() { ULL t = 2, iv = Mod * (t - Mod * Mod); iv *= t - Mod * iv, iv *= t - Mod * iv, iv *= t - Mod * iv; return iv * (t - Mod * iv); }
static constexpr ULL r2() { ULL iv = -Mod % Mod; for (int i = 0; i < 64; ++i) if ((iv *= 2) >= Mod) iv -= Mod; return iv; }
static ULL mul_high(ULL x, ULL y) { const ULL a = x >> 32, b = x & -1U, c = y >> 32, d = y & -1U, ad = a * d, bc = b * c; return a * c + (ad >> 32) + (bc >> 32) + (((ad & -1U) + (bc & -1U) + (b * d >> 32)) >> 32); }
// Montgomery reduction
static ULL redc_mul(ULL x, ULL y) { return norm(mul_high(x, y) - mul_high(x * y * R, Mod)); }
static constexpr ULL R = r();
static constexpr ULL R2 = r2();
public:
static unsigned long long mod() { return Mod; }
static ModLong from_raw(unsigned long long v) { return ModLong(private_constructor, redc_mul(v, R2)); }
static ModLong zero() { return ModLong(private_constructor, 0); }
static ModLong one() { return from_raw(1); }
bool is_zero() const { return *this == zero(); }
bool is_one() const { return *this == one(); }
ModLong() : v_() {}
template<typename Int, typename std::enable_if_t<std::is_signed_v<Int>, int> = 0> ModLong(Int v) : v_(redc_mul(safe_mod(v), R2)) {}
template<typename Int, typename std::enable_if_t<std::is_unsigned_v<Int>, int> = 0> ModLong(Int v) : v_(redc_mul(v % Mod, R2)) {}
unsigned long long val() const { return norm(-mul_high(v_ * R, Mod)); }
ModLong operator-() const { return ModLong(private_constructor, v_ == 0 ? v_ : Mod - v_); }
ModLong pow(long long e) const { if (e < 0) return inv().pow(-e); for (ModLong x(*this), res(from_raw(1));; x *= x) { if (e & 1) res *= x; if ((e >>= 1) == 0) return res; }}
ModLong inv() const { LL x1 = 1, x3 = 0, a = val(), b = Mod; while (b) { const LL q = a / b, x1_old = x1, a_old = a; x1 = x3, x3 = x1_old - x3 * q, a = b, b = a_old - b * q; } return from_raw(norm(x1)); }
ModLong div_by_2() const { if (v_ & 1) return ModLong(private_constructor, (v_ + Mod) >> 1); return ModLong(private_constructor, v_ >> 1); }
ModLong &operator+=(const ModLong &a) { v_ = norm(v_ + a.v_ - Mod); return *this; }
ModLong &operator-=(const ModLong &a) { v_ = norm(v_ - a.v_); return *this; }
ModLong &operator*=(const ModLong &a) { v_ = redc_mul(v_, a.v_); return *this; }
ModLong &operator/=(const ModLong &a) { return *this *= a.inv(); }
ModLong &operator++() { return *this += one(); }
ModLong operator++(int) { ModLong o(*this); *this += one(); return o; }
ModLong &operator--() { return *this -= one(); }
ModLong operator--(int) { ModLong o(*this); *this -= one(); return o; }
friend ModLong operator+(const ModLong &a, const ModLong &b) { return ModLong(a) += b; }
friend ModLong operator-(const ModLong &a, const ModLong &b) { return ModLong(a) -= b; }
friend ModLong operator*(const ModLong &a, const ModLong &b) { return ModLong(a) *= b; }
friend ModLong operator/(const ModLong &a, const ModLong &b) { return ModLong(a) /= b; }
friend bool operator==(const ModLong &a, const ModLong &b) { return a.v_ == b.v_; }
friend bool operator!=(const ModLong &a, const ModLong &b) { return a.v_ != b.v_; }
friend std::istream &operator>>(std::istream &a, ModLong &b) { LL v; a >> v; b.v_ = redc_mul(safe_mod(v), R2); return a; }
friend std::ostream &operator<<(std::ostream &a, const ModLong &b) { return a << b.val(); }
};
// clang-format on
#line 6 "conv_mod.hpp"
inline std::vector<int> convolution_mod(const std::vector<int> &a, const std::vector<int> &b,
int modular) {
using mint0 = ModLong<0x3F9A000000000001>;
using mint1 = ModLong<0x3FC6000000000001>;
const auto res0 =
convolution(std::vector<mint0>(a.begin(), a.end()), std::vector<mint0>(b.begin(), b.end()));
const auto res1 =
convolution(std::vector<mint1>(a.begin(), a.end()), std::vector<mint1>(b.begin(), b.end()));
const int n = res0.size();
std::vector<int> res(n);
const mint0 im1 = mint0(mint1::mod()).inv();
const int m1 = mint1::mod() % modular;
for (int i = 0; i < n; ++i) {
const mint0 k1 = (res0[i] - res1[i].val()) * im1;
res[i] = (k1.val() % modular * m1 + res1[i].val()) % modular;
}
return res;
}
#line 6 "test/convolution/convolution_mod_1000000007.0.test.cpp"
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<int> f(n), g(m);
for (int i = 0; i < n; ++i) std::cin >> f[i];
for (int i = 0; i < m; ++i) std::cin >> g[i];
const auto fg = convolution_mod(f, g, 1000000007);
for (int i = 0; i < (int)fg.size(); ++i) std::cout << fg[i] << ' ';
return 0;
}