$\prod_{i=0}^n f_i$
(fps/product_of_fps.hpp)

• View this file on GitHub
• Last update: 2023-10-26 11:41:06+09:00
• Include: #include "fps/product_of_fps.hpp"

説明

$\prod_{i = 0}^n f_i$ を $O(N(\log N)^2)$ で計算する。

Depends on

• modint/base.hpp

Required by

• $\sum_i (\sum_n A_n^i) x^i$ (fps/sums_of_powers.hpp)

Verified with

• test/polynomial/Product_of_Polynomial_Sequence.test.cpp
• test/yuki/yuki_1145.test.cpp

Code

#pragma once

#include <deque>
#include <vector>

#include "../modint/base.hpp"

namespace ebi {

template <Modint mint,
          std::vector<mint> (*convolution)(const std::vector<mint> &,
                                           const std::vector<mint> &)>
std::vector<mint> product_of_fps(const std::vector<std::vector<mint>> &fs) {
    if (fs.empty()) return {1};
    std::deque<std::vector<mint>> deque;
    for (auto &f : fs) deque.push_back(f);
    while (deque.size() > 1) {
        auto f = deque.front();
        deque.pop_front();
        auto g = deque.front();
        deque.pop_front();
        deque.push_back(convolution(f, g));
    }
    return deque.front();
}

}  // namespace ebi

#line 2 "fps/product_of_fps.hpp"

#include <deque>
#include <vector>

#line 2 "modint/base.hpp"

#include <concepts>
#include <iostream>
#include <utility>

namespace ebi {

template <class T>
concept Modint = requires(T a, T b) {
    a + b;
    a - b;
    a * b;
    a / b;
    a.inv();
    a.val();
    a.pow(std::declval<long long>());
    T::mod();
};

template <Modint mint> std::istream &operator>>(std::istream &os, mint &a) {
    long long x;
    os >> x;
    a = x;
    return os;
}

template <Modint mint>
std::ostream &operator<<(std::ostream &os, const mint &a) {
    return os << a.val();
}

}  // namespace ebi
#line 7 "fps/product_of_fps.hpp"

namespace ebi {

template <Modint mint,
          std::vector<mint> (*convolution)(const std::vector<mint> &,
                                           const std::vector<mint> &)>
std::vector<mint> product_of_fps(const std::vector<std::vector<mint>> &fs) {
    if (fs.empty()) return {1};
    std::deque<std::vector<mint>> deque;
    for (auto &f : fs) deque.push_back(f);
    while (deque.size() > 1) {
        auto f = deque.front();
        deque.pop_front();
        auto g = deque.front();
        deque.pop_front();
        deque.push_back(convolution(f, g));
    }
    return deque.front();
}

}  // namespace ebi

Back to top page