Combination (Pascal)
(math/combination/pascal.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "math/combination/pascal.hpp"

概要

$C$, $P$, $H$をパスカルの三角形を用いて求める.

計算量

• クエリ : $O(r)$

使用例

• C_pascal<modint>(n, r) : modint型で$C(n, r)$に答える

Verified with

• test/aoj/1501.combination.pascal.test.cpp

Code

/**
 * @brief Combination (Pascal)
 * @docs docs/math/combination/pascal.md
 */

template <typename T>
T C_pascal(long long n, int r) {
    if (r == 0) return T(1);
    if (r < 0) return T(0);
    if (n < 0) return T(r & 1 ? -1 : 1) * C_pascal<T>(-n + r - 1, r);
    if (n == 0 || n < r) return T(0);
    T ret(1);
    for (int i = 1; i <= r; ++i) ret *= n--, ret /= i;
    return ret;
}

template <typename T>
T P_pascal(long long n, int r) {
    if (n < r || r < 0) return T(0);
    T ret(1);
    for (int i = 1; i <= r; ++i) ret *= n--;
    return ret;
}

template <typename T>
T H_pascal(long long n, int r) {
    if (n < 0 || r < 0) return T(0);
    if (!n && !r) return T(1);
    return C_pascal<T>(n + r - 1, r);
}

#line 1 "math/combination/pascal.hpp"
/**
 * @brief Combination (Pascal)
 * @docs docs/math/combination/pascal.md
 */

template <typename T>
T C_pascal(long long n, int r) {
    if (r == 0) return T(1);
    if (r < 0) return T(0);
    if (n < 0) return T(r & 1 ? -1 : 1) * C_pascal<T>(-n + r - 1, r);
    if (n == 0 || n < r) return T(0);
    T ret(1);
    for (int i = 1; i <= r; ++i) ret *= n--, ret /= i;
    return ret;
}

template <typename T>
T P_pascal(long long n, int r) {
    if (n < r || r < 0) return T(0);
    T ret(1);
    for (int i = 1; i <= r; ++i) ret *= n--;
    return ret;
}

template <typename T>
T H_pascal(long long n, int r) {
    if (n < 0 || r < 0) return T(0);
    if (!n && !r) return T(1);
    return C_pascal<T>(n + r - 1, r);
}

Back to top page