Online Convolution
(convolution/online_convolution.hpp)

• View this file on GitHub
• Last update: 2023-12-28 15:52:36+09:00
• Include: #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に依存しているため使用するときは注意。

Depends on

• template/int_alias.hpp

Verified with

• test/convolution/Online_Convolution.test.cpp
• test/yuki/yuki_2633.test.cpp

Code

#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

Back to top page