Catalan's Convolution Formula
(math/catalan_convolution.hpp)

• View this file on GitHub
• Last update: 2025-04-09 23:43:03+09:00
• Include: #include "math/catalan_convolution.hpp"

説明

$C(x)$ をカタラン数の母関数として、 $[x^n] C(x)^k$ を求める。前計算 $O(N)$ クエリ $O(1)$ 。

Depends on

• Binomial Coefficient (math/binomial.hpp)
• modint/base.hpp

Verified with

• test/math/Catalan_Convolution.test.cpp

Code

#pragma once

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

namespace ebi {

template <Modint mint> mint catalan_convolution(int pow, int n) {
    return Binomial<mint>::c(n + n + pow - 1, n) * pow *
           Binomial<mint>::inv(n + pow);
}

}  // namespace ebi

#line 2 "math/catalan_convolution.hpp"

#line 2 "math/binomial.hpp"

#include <bit>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <ranges>
#include <vector>

#line 2 "modint/base.hpp"

#include <concepts>
#line 5 "modint/base.hpp"
#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 11 "math/binomial.hpp"

namespace ebi {

template <Modint mint> struct Binomial {
  private:
    static void extend(int len = -1) {
        int sz = (int)fact.size();
        if (len < 0)
            len = 2 * sz;
        else if (len <= sz)
            return;
        else
            len = std::max(2 * sz, (int)std::bit_ceil(std::uint32_t(len)));
        len = std::min(len, mint::mod());
        assert(sz <= len);
        fact.resize(len);
        inv_fact.resize(len);
        for (int i : std::views::iota(sz, len)) {
            fact[i] = fact[i - 1] * i;
        }
        inv_fact[len - 1] = fact[len - 1].inv();
        for (int i : std::views::iota(sz, len) | std::views::reverse) {
            inv_fact[i - 1] = inv_fact[i] * i;
        }
    }

  public:
    Binomial() = default;

    Binomial(int n) {
        extend(n + 1);
    }

    static mint f(int n) {
        if (n < 0) [[unlikely]] {
            return 0;
        }
        if (n >= (int)fact.size()) [[unlikely]] {
            extend(n + 1);
        }
        return fact[n];
    }

    static mint inv_f(int n) {
        if (n < 0) [[unlikely]] {
            return 0;
        }
        if (n >= (int)fact.size()) [[unlikely]] {
            extend(n + 1);
        }
        return inv_fact[n];
    }

    static mint c(int n, int r) {
        if (r < 0 || n < r) return 0;
        return f(n) * inv_f(r) * inv_f(n - r);
    }

    static mint neg_c(int k, int d) {
        assert(d > 0);
        return c(k + d - 1, d - 1);
    }

    static mint p(int n, int r) {
        if (r < 0 || n < r) return 0;
        return f(n) * inv_f(n - r);
    }

    static mint catalan_number(int n) {
        return c(2 * n, n) * inv(n + 1);
    }

    static mint inv(int n) {
        return inv_f(n) * f(n - 1);
    }

    static void reserve(int n) {
        extend(n + 1);
    }

  private:
    static std::vector<mint> fact, inv_fact;
};

template <Modint mint>
std::vector<mint> Binomial<mint>::fact = std::vector<mint>(2, 1);

template <Modint mint>
std::vector<mint> Binomial<mint>::inv_fact = std::vector<mint>(2, 1);

}  // namespace ebi
#line 5 "math/catalan_convolution.hpp"

namespace ebi {

template <Modint mint> mint catalan_convolution(int pow, int n) {
    return Binomial<mint>::c(n + n + pow - 1, n) * pow *
           Binomial<mint>::inv(n + pow);
}

}  // namespace ebi

Back to top page