Src/FPS/FPS.hpp

• View this file on GitHub
• Last update: 2026-01-03 20:52:40+09:00
• Include: #include "Src/FPS/FPS.hpp"

Depends on

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

Required by

• $[x^{N}]\frac{P(x)}{Q(x)}$ の高速計算 (Bostan-Mori アルゴリズム) (Src/FPS/BostanMori.hpp)
• Src/FPS/DivisionOfPolynomials.hpp
• Src/FPS/FPSNTTFriendly.hpp
• 線形漸化式のK項目を計算する (Src/FPS/KthTerm.hpp)
• 次数の総和が抑えられている多項式の列の総積 (Src/FPS/PolynomialProducts.hpp)
• Polynomial Taylor Shift (Src/FPS/PolynomialTaylorShift.hpp)
• FPS Power Projection (Src/FPS/PowerProjection.hpp)
• 次数の総和が抑えられている有理式の総和 (Src/FPS/RationalSum.hpp)

Verified with

• ABC215-G Colorful Candies 2 (Test/AtCoder/abc215_g.test.cpp)
• Test/AtCoder/abc345_g.test.cpp
• Test/AtCoder/abc385_g.test.cpp
• ABC436-G Linear Inequation (Test/AtCoder/abc436_g.test.cpp)
• Test/AtCoder/abc439_g.test.cpp
• Test/AtCoder/tdpc_fibonacci.test.cpp
• Test/LC/division_of_polynomials.test.cpp
• Test/LC/exp_of_formal_power_series.test.cpp
• Test/LC/inv_of_formal_power_series.test.cpp
• Test/LC/kth_term_of_linearly_recurrent_sequence.test.cpp
• Test/LC/log_of_formal_power_series.test.cpp
• Test/LC/polynomial_taylor_shift.test.cpp
• Test/LC/pow_of_formal_power_series.test.cpp
• Test/LC/product_of_polynomial_sequence.test.cpp
• Test/My/FPS/PowerProjection.test.cpp
• Test/yukicoder/3044.test.cpp

Code

#pragma once

#include "../Template/TypeAlias.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 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

Back to top page