次数の総和が抑えられている多項式の列の総積
(Src/FPS/PolynomialProducts.hpp)

• View this file on GitHub
• Last update: 2026-01-12 19:02:30+09:00
• Include: #include "Src/FPS/PolynomialProducts.hpp"

概要

ライブラリの説明

template <concepts::IndexedFPS FPS, class Conv = FPSMult>
requires concepts::Convolution<FPS, Conv>
FPS PolynomialProducts(std::vector<FPS> F, Conv convolution = {}) {

convはFPSNTTFriendlyのときは何も指定しなくても良い。それ以外のときは畳み込みをする関数オブジェクトを与える。

$\Theta O(NM)$ の畳み込みはFPS.hppのNaiveConvolutionを与えると良い。

計算量: 次数の総和を $N$ として $O(N\log^2 N)$ (畳み込みが $O(n\log n)$ であることを前提)

Depends on

• Src/FPS/FPS.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/AtCoder/abc385_g.test.cpp
• Test/LC/product_of_polynomial_sequence.test.cpp

Code

#pragma once

#include "FPS.hpp"

#include <vector>

namespace zawa {

template <concepts::IndexedFPS FPS, class Conv = FPSMult>
requires concepts::Convolution<FPS, Conv>
FPS PolynomialProducts(std::vector<FPS> F, Conv convolution = {}) {
    if (F.empty())
        return {1};
    auto rec = [&](auto rec, usize l, usize r) -> void {
        if (l + 1 >= r)
            return;
        const usize md = (l + r) >> 1;
        rec(rec, l, md);
        rec(rec, md, r);
        F[l] = convolution(F[l], F[md]);
    };
    rec(rec, 0u, F.size());
    return F[0];
}

} // namespace zawa

#line 2 "Src/FPS/PolynomialProducts.hpp"

#line 2 "Src/FPS/FPS.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/FPS/FPS.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class FPS>
concept IndexedFPS = requires(FPS f, usize i) {
    typename FPS::value_type;
    { f.size() } -> std::convertible_to<usize>;
    { f[i] } -> std::convertible_to<typename FPS::value_type>;
    f.reserve(0);
    f.push_back(f[i]);
};

template <class FPS, class Conv>
concept Convolution = 
    std::regular_invocable<Conv, const FPS&, const FPS&> &&
    std::same_as<std::invoke_result_t<Conv, const FPS&, const FPS&>, FPS>;

} // namespace concepts

struct FPSMult {
    template <class FPS>
    requires requires(const FPS& a, const FPS& b) {
        { a * b } -> std::same_as<FPS>;
    }
    FPS operator()(const FPS& a, const FPS& b) const {
        return a * b;
    }
};

struct NaiveConvolution {
    template <class FPS>
    FPS operator()(const FPS& a, const FPS& b) const {
        if (a.empty())
            return b;
        if (b.empty())
            return a;
        FPS res(a.size() + b.size() - 1);
        for (usize i = 0 ; i < a.size() ; i++)
            for (usize j = 0 ; j < b.size() ; j++)
                res[i + j] += a[i] * b[j];
        return res;
    }
};

} // namespace zawa
#line 4 "Src/FPS/PolynomialProducts.hpp"

#include <vector>

namespace zawa {

template <concepts::IndexedFPS FPS, class Conv = FPSMult>
requires concepts::Convolution<FPS, Conv>
FPS PolynomialProducts(std::vector<FPS> F, Conv convolution = {}) {
    if (F.empty())
        return {1};
    auto rec = [&](auto rec, usize l, usize r) -> void {
        if (l + 1 >= r)
            return;
        const usize md = (l + r) >> 1;
        rec(rec, l, md);
        rec(rec, md, r);
        F[l] = convolution(F[l], F[md]);
    };
    rec(rec, 0u, F.size());
    return F[0];
}

} // namespace zawa

Back to top page