次数の総和が抑えられている有理式の総和
(Src/FPS/RationalSum.hpp)

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

概要

ライブラリの説明

template <concepts::IndexedFPS FPS, class Conv = FPSMult>
requires concepts::Convolution<FPS, Conv>
std::pair<FPS, FPS> RationalSum(std::vector<FPS> num, std::vector<FPS> den, Conv conv = {})

num.size() == den.size()が必要である。denのある要素が $0$ であるとき、返り値は共に $0$ になると予想される(チェックはしていない)

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/abc439_g.test.cpp

Code

#pragma once

#include "FPS.hpp"

#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

template <concepts::IndexedFPS FPS, class Conv = FPSMult>
requires concepts::Convolution<FPS, Conv>
std::pair<FPS, FPS> RationalSum(std::vector<FPS> num, std::vector<FPS> den, Conv conv = {}) {
    assert(num.size() == den.size());
    if (num.empty())
        return std::pair<FPS, FPS>{{0}, {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);
        num[l] = conv(num[l], den[md]) + conv(num[md], den[l]);
        den[l] = conv(den[l], den[md]);
    };
    rec(rec, 0u, num.size());
    return std::pair{num[0], den[0]};
}

} // namespace zawa

#line 2 "Src/FPS/RationalSum.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/RationalSum.hpp"

#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

template <concepts::IndexedFPS FPS, class Conv = FPSMult>
requires concepts::Convolution<FPS, Conv>
std::pair<FPS, FPS> RationalSum(std::vector<FPS> num, std::vector<FPS> den, Conv conv = {}) {
    assert(num.size() == den.size());
    if (num.empty())
        return std::pair<FPS, FPS>{{0}, {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);
        num[l] = conv(num[l], den[md]) + conv(num[md], den[l]);
        den[l] = conv(den[l], den[md]);
    };
    rec(rec, 0u, num.size());
    return std::pair{num[0], den[0]};
}

} // namespace zawa

Back to top page