test/src/convolution/relaxed_convolution/abc230_h.test.cpp

• View this file on GitHub
• Last update: 2023-07-09 04:04:16+09:00
• Problem: https://atcoder.jp/contests/abc230/tasks/abc230_h

Depends on

• Relaxed Convolution (library/convolution/relaxed_convolution.hpp)
• 逆元テーブル (library/math/inv_mods.hpp)

Code

#define PROBLEM "https://atcoder.jp/contests/abc230/tasks/abc230_h"

#include <iostream>

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

using mint = atcoder::modint998244353;

#include "library/math/inv_mods.hpp"
#include "library/convolution/relaxed_convolution.hpp"

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

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

    std::vector<mint> c(n + 1);
    for (int i = 0; i < m; ++i) {
        int w;
        std::cin >> w;
        c[w] = 1;
    }
    suisen::inv_mods<mint> invs(n);

    suisen::RelaxedConvolution<mint> h{ [](const auto& f, const auto &g) { return atcoder::convolution(f, g); } };

    std::vector<mint> f(n), g(n);
    for (int w = 1; w < n; ++w) {
        for (int i = 1; i * w - 1 < n; ++i) {
            g[i * w - 1] += w * (f[w - 1] + c[w]);
        }
        f[w] = h.append((w == 1) + f[w - 1], g[w - 1]) * invs[w];
    }
    f.erase(f.begin());

    for (const auto &e : f) {
        std::cout << e.val() << '\n';
    }

    return 0;
}

#line 1 "test/src/convolution/relaxed_convolution/abc230_h.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc230/tasks/abc230_h"

#include <iostream>

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

using mint = atcoder::modint998244353;

#line 1 "library/math/inv_mods.hpp"



#include <vector>

namespace suisen {
    template <typename mint>
    class inv_mods {
    public:
        inv_mods() = default;
        inv_mods(int n) { ensure(n); }
        const mint& operator[](int i) const {
            ensure(i);
            return invs[i];
        }
        static void ensure(int n) {
            int sz = invs.size();
            if (sz < 2) invs = { 0, 1 }, sz = 2;
            if (sz < n + 1) {
                invs.resize(n + 1);
                for (int i = sz; i <= n; ++i) invs[i] = mint(mod - mod / i) * invs[mod % i];
            }
        }
    private:
        static std::vector<mint> invs;
        static constexpr int mod = mint::mod();
    };
    template <typename mint>
    std::vector<mint> inv_mods<mint>::invs{};

    template <typename mint>
    std::vector<mint> get_invs(const std::vector<mint>& vs) {
        const int n = vs.size();

        mint p = 1;
        for (auto& e : vs) {
            p *= e;
            assert(e != 0);
        }
        mint ip = p.inv();

        std::vector<mint> rp(n + 1);
        rp[n] = 1;
        for (int i = n - 1; i >= 0; --i) {
            rp[i] = rp[i + 1] * vs[i];
        }
        std::vector<mint> res(n);
        for (int i = 0; i < n; ++i) {
            res[i] = ip * rp[i + 1];
            ip *= vs[i];
        }
        return res;
    }
}


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



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

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 12 "test/src/convolution/relaxed_convolution/abc230_h.test.cpp"

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

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

    std::vector<mint> c(n + 1);
    for (int i = 0; i < m; ++i) {
        int w;
        std::cin >> w;
        c[w] = 1;
    }
    suisen::inv_mods<mint> invs(n);

    suisen::RelaxedConvolution<mint> h{ [](const auto& f, const auto &g) { return atcoder::convolution(f, g); } };

    std::vector<mint> f(n), g(n);
    for (int w = 1; w < n; ++w) {
        for (int i = 1; i * w - 1 < n; ++i) {
            g[i * w - 1] += w * (f[w - 1] + c[w]);
        }
        f[w] = h.append((w == 1) + f[w - 1], g[w - 1]) * invs[w];
    }
    f.erase(f.begin());

    for (const auto &e : f) {
        std::cout << e.val() << '\n';
    }

    return 0;
}

Back to top page