This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "convolution/online_convolution.hpp"
$c = a \times b$ とする。 $a_i, b_i$ を与えて、 $c_i$ を返すという操作を $i = 0$ からオンラインで処理する。最終的な $c$ の長さを $N$ とすると、計算量は $O(N(\log N)^2)$ となる。
ACLに依存しているため使用するときは注意。
#pragma once #include <atcoder/convolution> #include <atcoder/modint> #include <bit> #include <vector> #include "../template/int_alias.hpp" namespace ebi { struct online_convolution { private: using mint = atcoder::modint998244353; public: online_convolution() = default; mint add(int idx, mint ai, mint bi) { assert(p == idx); a.emplace_back(ai); b.emplace_back(bi); int z = std::countr_zero(u32(p + 2)), w = 1 << z; if (p + 2 == w) { auto a0 = a; a0.resize(2 * w); atcoder::internal::butterfly(a0); fa.emplace_back(a0.begin(), a0.begin() + w); auto b0 = b; b0.resize(2 * w); atcoder::internal::butterfly(b0); fb.emplace_back(b0.begin(), b0.begin() + w); for (int i = 0; i < 2 * w; i++) a0[i] *= b0[i]; atcoder::internal::butterfly_inv(a0); mint inv_len = mint(2 * w).inv(); c.resize(2 * p + 2); for (int i = 0; i < p + 1; i++) c[p + i] += a0[p + i] * inv_len; } else { std::vector<mint> a0 = {a.end() - w, a.end()}; a0.resize(2 * w); atcoder::internal::butterfly(a0); std::vector<mint> b0 = {b.end() - w, b.end()}; b0.resize(2 * w); atcoder::internal::butterfly(b0); for (int i = 0; i < 2 * w; i++) { a0[i] = a0[i] * fb[z][i] + fa[z][i] * b0[i]; } atcoder::internal::butterfly_inv(a0); mint inv_len = mint(2 * w).inv(); for (int i = 0; i < w; i++) c[p + i] += a0[w - 1 + i] * inv_len; } return c[p++]; } mint operator[](int i) const { assert(0 <= i && i < p); return c[i]; } private: int p = 0; std::vector<mint> a, b, c; std::vector<std::vector<mint>> fa, fb; }; } // namespace ebi
#line 2 "convolution/online_convolution.hpp" #include <atcoder/convolution> #include <atcoder/modint> #include <bit> #include <vector> #line 2 "template/int_alias.hpp" #include <cstdint> namespace ebi { using ld = long double; using std::size_t; using i8 = std::int8_t; using u8 = std::uint8_t; using i16 = std::int16_t; using u16 = std::uint16_t; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; } // namespace ebi #line 9 "convolution/online_convolution.hpp" namespace ebi { struct online_convolution { private: using mint = atcoder::modint998244353; public: online_convolution() = default; mint add(int idx, mint ai, mint bi) { assert(p == idx); a.emplace_back(ai); b.emplace_back(bi); int z = std::countr_zero(u32(p + 2)), w = 1 << z; if (p + 2 == w) { auto a0 = a; a0.resize(2 * w); atcoder::internal::butterfly(a0); fa.emplace_back(a0.begin(), a0.begin() + w); auto b0 = b; b0.resize(2 * w); atcoder::internal::butterfly(b0); fb.emplace_back(b0.begin(), b0.begin() + w); for (int i = 0; i < 2 * w; i++) a0[i] *= b0[i]; atcoder::internal::butterfly_inv(a0); mint inv_len = mint(2 * w).inv(); c.resize(2 * p + 2); for (int i = 0; i < p + 1; i++) c[p + i] += a0[p + i] * inv_len; } else { std::vector<mint> a0 = {a.end() - w, a.end()}; a0.resize(2 * w); atcoder::internal::butterfly(a0); std::vector<mint> b0 = {b.end() - w, b.end()}; b0.resize(2 * w); atcoder::internal::butterfly(b0); for (int i = 0; i < 2 * w; i++) { a0[i] = a0[i] * fb[z][i] + fa[z][i] * b0[i]; } atcoder::internal::butterfly_inv(a0); mint inv_len = mint(2 * w).inv(); for (int i = 0; i < w; i++) c[p + i] += a0[w - 1 + i] * inv_len; } return c[p++]; } mint operator[](int i) const { assert(0 <= i && i < p); return c[i]; } private: int p = 0; std::vector<mint> a, b, c; std::vector<std::vector<mint>> fa, fb; }; } // namespace ebi