test/src/convolution/relaxed_convolution/convolution_mod.test.cpp

• View this file on GitHub
• Last update: 2022-06-07 17:31:21+09:00
• Problem: https://judge.yosupo.jp/problem/convolution_mod

Depends on

• Relaxed Convolution (library/convolution/relaxed_convolution.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/convolution_mod"

#include <iostream>

#include <atcoder/modint>
#include <atcoder/convolution>

using mint = atcoder::modint998244353;

std::istream& operator>>(std::istream& in, mint& a) {
    long long e; in >> e; a = e;
    return in;
}

std::ostream& operator<<(std::ostream& out, const mint& a) {
    out << a.val();
    return out;
}

#include "library/convolution/relaxed_convolution.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::size_t n, m;
    std::cin >> n >> m;

    std::vector<mint> a(n), b(m);
    for (auto& e : a) std::cin >> e;
    for (auto& e : b) std::cin >> e;

    suisen::RelaxedConvolution<mint> conv{ [](const auto& a, const auto& b) { return atcoder::convolution(a, b); } };

    for (std::size_t i = 0; i < n + m - 1; ++i) {
        conv.append(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
    }
    auto c = conv.get();
    for (std::size_t i = 0; i < n + m - 1; ++i) {
        std::cout << c[i] << " \n"[i == n + m - 2];
    }
    return 0;
}

#line 1 "test/src/convolution/relaxed_convolution/convolution_mod.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/convolution_mod"

#include <iostream>

#include <atcoder/modint>
#include <atcoder/convolution>

using mint = atcoder::modint998244353;

std::istream& operator>>(std::istream& in, mint& a) {
    long long e; in >> e; a = e;
    return in;
}

std::ostream& operator<<(std::ostream& out, const mint& a) {
    out << a.val();
    return out;
}

#line 1 "library/convolution/relaxed_convolution.hpp"



#include <vector>

namespace suisen {
    // reference: https://qiita.com/Kiri8128/items/1738d5403764a0e26b4c
    template <typename T>
    struct RelaxedConvolution {
        using value_type = T;
        using polynomial_type = std::vector<value_type>;
        using convolution_type = polynomial_type(*)(const polynomial_type&, const polynomial_type&);

        RelaxedConvolution() = default;
        RelaxedConvolution(const convolution_type &convolve) : _convolve(convolve), _n(0), _f{}, _g{}, _h{} {}

        void set_convolve_function(const convolution_type &convolve) {
            _convolve = convolve;
        }

        value_type append(const value_type &fi, const value_type &gi) {
            ++_n;
            _f.push_back(fi), _g.push_back(gi);
            for (int p = 1;; p <<= 1) {
                int l1 = _n - p, r1 = _n, l2 = p - 1, r2 = l2 + p;
                add(l1 + l2, range_convolve(l1, r1, l2, r2));
                if (l1 == l2) break;
                add(l1 + l2, range_convolve(l2, r2, l1, r1));
                if (not (_n & p)) break;
            }
            return _h[_n - 1];
        }

        const value_type& operator[](int i) const {
            return _h[i];
        }
        polynomial_type get() const {
            return _h;
        }

    private:
        convolution_type _convolve = [](const polynomial_type&, const polynomial_type&) -> polynomial_type { assert(false); };
        int _n;
        polynomial_type _f, _g, _h;

        polynomial_type range_convolve(int l1, int r1, int l2, int r2) {
            return _convolve(polynomial_type(_f.begin() + l1, _f.begin() + r1), polynomial_type(_g.begin() + l2, _g.begin() + r2));
        }

        void add(std::size_t bias, const polynomial_type &h) {
            if (_h.size() < bias + h.size()) _h.resize(bias + h.size());
            for (std::size_t i = 0; i < h.size(); ++i) _h[bias + i] += h[i];
        }
    };
} // namespace suisen



#line 21 "test/src/convolution/relaxed_convolution/convolution_mod.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::size_t n, m;
    std::cin >> n >> m;

    std::vector<mint> a(n), b(m);
    for (auto& e : a) std::cin >> e;
    for (auto& e : b) std::cin >> e;

    suisen::RelaxedConvolution<mint> conv{ [](const auto& a, const auto& b) { return atcoder::convolution(a, b); } };

    for (std::size_t i = 0; i < n + m - 1; ++i) {
        conv.append(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
    }
    auto c = conv.get();
    for (std::size_t i = 0; i < n + m - 1; ++i) {
        std::cout << c[i] << " \n"[i == n + m - 2];
    }
    return 0;
}

Back to top page