cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub NotLeonian/cp-library-cpp

:heavy_check_mark: test/src/convolution/lcm_convolution/lcm_convolution.test.cpp

Depends on

Code

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

#include <iostream>
#include <atcoder/modint>

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/lcm_convolution.hpp"


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

    int n;
    std::cin >> n;

    std::vector<mint> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i) std::cin >> a[i];
    for (int i = 1; i <= n; ++i) std::cin >> b[i];

    std::vector<mint> c = suisen::lcm_convolution(a, b);
    for (int i = 1; i <= n; ++i) std::cout << c[i] << " \n"[i == n];

    return 0;
}
#line 1 "test/src/convolution/lcm_convolution/lcm_convolution.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lcm_convolution"

#include <iostream>
#include <atcoder/modint>

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/lcm_convolution.hpp"



#line 1 "library/transform/divisor.hpp"



#include <vector>
#line 1 "library/util/default_operator.hpp"



namespace suisen {
    namespace default_operator {
        template <typename T>
        auto zero() -> decltype(T { 0 }) { return T { 0 }; }
        template <typename T>
        auto one()  -> decltype(T { 1 }) { return T { 1 }; }
        template <typename T>
        auto add(const T &x, const T &y) -> decltype(x + y) { return x + y; }
        template <typename T>
        auto sub(const T &x, const T &y) -> decltype(x - y) { return x - y; }
        template <typename T>
        auto mul(const T &x, const T &y) -> decltype(x * y) { return x * y; }
        template <typename T>
        auto div(const T &x, const T &y) -> decltype(x / y) { return x / y; }
        template <typename T>
        auto mod(const T &x, const T &y) -> decltype(x % y) { return x % y; }
        template <typename T>
        auto neg(const T &x) -> decltype(-x) { return -x; }
        template <typename T>
        auto inv(const T &x) -> decltype(one<T>() / x)  { return one<T>() / x; }
    } // default_operator
    namespace default_operator_noref {
        template <typename T>
        auto zero() -> decltype(T { 0 }) { return T { 0 }; }
        template <typename T>
        auto one()  -> decltype(T { 1 }) { return T { 1 }; }
        template <typename T>
        auto add(T x, T y) -> decltype(x + y) { return x + y; }
        template <typename T>
        auto sub(T x, T y) -> decltype(x - y) { return x - y; }
        template <typename T>
        auto mul(T x, T y) -> decltype(x * y) { return x * y; }
        template <typename T>
        auto div(T x, T y) -> decltype(x / y) { return x / y; }
        template <typename T>
        auto mod(T x, T y) -> decltype(x % y) { return x % y; }
        template <typename T>
        auto neg(T x) -> decltype(-x) { return -x; }
        template <typename T>
        auto inv(T x) -> decltype(one<T>() / x)  { return one<T>() / x; }
    } // default_operator
} // namespace suisen


#line 6 "library/transform/divisor.hpp"

namespace suisen::divisor_transform {
    // Calculates `g` s.t. g(n) = Sum_{d | n} f(d) inplace.
    template <typename T, auto add = default_operator::add<T>>
    void zeta(std::vector<T> &f) {
        const int n = f.size();
        std::vector<char> is_prime(n, true);
        auto cum = [&](const int p) {
            for (int q = 1, pq = p; pq < n; ++q, pq += p) {
                f[pq] = add(f[pq], f[q]);
                is_prime[pq] = false;
            }
        };
        for (int p = 2; p < n; ++p) if (is_prime[p]) cum(p);
    }
    // Calculates `f` s.t. g(n) = Sum_{d | n} f(d) inplace.
    template <typename T, auto sub = default_operator::sub<T>>
    void mobius(std::vector<T> &f) {
        const int n = f.size();
        std::vector<char> is_prime(n, true);
        auto diff = [&](const int p) {
            const int qmax = (n - 1) / p, rmax = qmax * p;
            for (int q = qmax, pq = rmax; q >= 1; --q, pq -= p) {
                f[pq] = sub(f[pq], f[q]);
                is_prime[pq] = false;
            }
        };
        for (int p = 2; p < n; ++p) if (is_prime[p]) diff(p);
    }
} // namespace suisen::divisor_transform


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



#include <cassert>
#line 6 "library/convolution/convolution.hpp"

#line 8 "library/convolution/convolution.hpp"

namespace suisen {
    namespace convolution {
        template <typename T, auto transform, auto inv_transform, auto mul = default_operator::mul<T>>
        std::vector<T> transform_convolution(std::vector<T> a, std::vector<T> b) {
            const std::size_t n = a.size(), m = b.size();
            assert(n == m);
            transform(a), transform(b);
            for (std::size_t i = 0; i < n; ++i) a[i] = mul(a[i], b[i]);
            inv_transform(a);
            return a;
        }
        template <typename T, auto transform, auto inv_transform, auto mul = default_operator::mul<T>>
        std::vector<T> transform_convolution(std::vector<std::vector<T>> a) {
            const std::size_t num = a.size();
            assert(num);
            const std::size_t n = a[0].size();
            for (auto &v : a) {
                assert(n == int(v.size()));
                transform(v);
            }
            auto &res = a[0];
            for (int i = 1; i < num; ++i) {
                for (int j = 0; j < n; ++j) res[j] = mul(res[j], a[i][j]);
            }
            inv_transform(res);
            return res;
        }
    }
} // namespace suisen



#line 6 "library/convolution/lcm_convolution.hpp"

namespace suisen {
    template <
        typename T,
        auto add = default_operator::add<T>,
        auto sub = default_operator::sub<T>,
        auto mul = default_operator::mul<T>
    >
    auto lcm_convolution(std::vector<T> a, std::vector<T> b) {
        return convolution::transform_convolution<
            T,
            divisor_transform::zeta<T, add>,
            divisor_transform::mobius<T, sub>,
            mul
        >(std::move(a), std::move(b));
    }
} // namespace suisen


#line 19 "test/src/convolution/lcm_convolution/lcm_convolution.test.cpp"


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

    int n;
    std::cin >> n;

    std::vector<mint> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i) std::cin >> a[i];
    for (int i = 1; i <= n; ++i) std::cin >> b[i];

    std::vector<mint> c = suisen::lcm_convolution(a, b);
    for (int i = 1; i <= n; ++i) std::cout << c[i] << " \n"[i == n];

    return 0;
}
Back to top page