This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "math/catalan_convolution.hpp"
$C(x)$ をカタラン数の母関数として、 $[x^n] C(x)^k$ を求める。前計算 $O(N)$ クエリ $O(1)$ 。
#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 <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 10 "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 >= (int)fact.size()) [[unlikely]] { extend(n + 1); } return fact[n]; } static mint inv_f(int n) { 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 p(int n, int r) { if (r < 0 || n < r) return 0; return f(n) * inv_f(n - r); } 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