順列，組合せ，重複組合せ
(algorithm/Math/Combinatorics/naive_combination.hpp)

• View this file on GitHub
• Last update: 2025-08-31 07:47:07+00:00
• Include: #include "algorithm/Math/Combinatorics/naive_combination.hpp"

概要

順列，組合せ，重複組合せの総数を $\mathcal{O}(K)$ で数え上げる．

順列

\[{}_n \mathrm{P}_k = n \times (n-1) \times (n-2) \times \cdots \times (n-k+1)\]

組合せ

\[\begin{equation} {}_n \mathrm{C}_k = \begin{cases} 0 & \text{if $n<k$,} \\ {}_n \mathrm{P}_k / k! & \text{otherwise} \end{cases} \notag \end{equation}\]

重複組合せ

\[\begin{equation} {}_n \mathrm{H}_k = \begin{cases} 1 & \text{if $k=0$,} \\ 0 & \text{if $n=0$ and $k>0$,} \\ {}_{k+n-1} \mathrm{C}_k & \text{otherwise} \end{cases} \notag \end{equation}\]

参考文献

1. “数え上げ数学”. Wikipedia. https://ja.wikipedia.org/wiki/数え上げ数学.
2. “組合せ数学”. Wikipedia. https://ja.wikipedia.org/wiki/組合せ数学.
3. “順列”. Wikipedia. https://ja.wikipedia.org/wiki/順列.
4. “組合せ (数学)”. Wikipedia. https://ja.wikipedia.org/wiki/組合せ_(数学).
5. “重複組合せ”. Wikipedia. https://ja.wikipedia.org/wiki/重複組合せ.

問題

• “D - 表現の自由 ( Freedom of expression )”. AtCoder Regular Contest 004. https://atcoder.jp/contests/arc004/tasks/arc004_4.
• “D - 多重ループ”. AtCoder Beginner Contest 021. https://atcoder.jp/contests/abc021/tasks/abc021_d.

Depends on

• モジュラ逆数（乗法逆元） (algorithm/Math/ModularArithmetic/mod_inv.hpp)
• algorithm/Math/ModularArithmetic/modulo.hpp

Code

#ifndef ALGORITHM_NAIVE_COMBINATION_HPP
#define ALGORITHM_NAIVE_COMBINATION_HPP 1

#include <algorithm>
#include <cassert>

#include "../ModularArithmetic/mod_inv.hpp"

namespace algorithm {

// 順列．O(K).
constexpr long long nPk(long long n, long long k) {
    assert(n >= 0);
    assert(k >= 0);
    if(n < k) return 0;
    long long res = 1;
    for(long long i = 0; i < k; ++i) res *= (n - i);
    return res;
}

// 順列（mod付き）．O(K).
constexpr long long nPk(long long n, long long k, int mod) {
    assert(n >= 0);
    assert(k >= 0);
    assert(mod >= 1);
    if(n < k) return 0;
    n %= mod;
    long long res = 1 % mod;
    for(long long i = 0; i < k; ++i) {
        long long tmp = n - i;
        if(tmp < 0) tmp += mod;
        res = res * tmp % mod;
    }
    return res;
}

// 組合せ．O(min(K,N-K)).
constexpr long long nCk(long long n, long long k) {
    assert(n >= 0);
    assert(k >= 0);
    if(n < k) return 0;
    k = std::min(k, n - k);
    long long res = 1;
    for(long long i = 0; i < k; ++i) res = res * (n - i) / (i + 1);
    return res;
}

// 組合せ（mod付き）．
constexpr long long nCk(long long n, long long k, int mod) {
    assert(n >= 0);
    assert(k >= 0);
    assert(mod >= 1);
    if(n < k) return 0;
    k = std::min(k, n - k);
    return nPk(n, k, mod) * mod_inv(nPk(k, k, mod), mod) % mod;
}

// 重複組合せ．O(min(N-1,K)).
constexpr long long nHk(long long n, long long k) {
    assert(n >= 0);
    assert(k >= 0);
    if(k == 0) return 1;
    if(n == 0) return 0;
    return nCk(k + n - 1, k);
}

// 重複組合せ（mod付き）．
constexpr long long nHk(long long n, long long k, int mod) {
    assert(n >= 0);
    assert(k >= 0);
    assert(mod >= 1);
    if(k == 0) return 1 % mod;
    if(n == 0) return 0;
    return nCk(k + n - 1, k, mod);
}

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/Combinatorics/naive_combination.hpp"



#include <algorithm>
#include <cassert>

#line 1 "algorithm/Math/ModularArithmetic/mod_inv.hpp"



#line 5 "algorithm/Math/ModularArithmetic/mod_inv.hpp"
#include <concepts>
#include <cstdint>
#include <utility>

#line 1 "algorithm/Math/ModularArithmetic/modulo.hpp"



#line 6 "algorithm/Math/ModularArithmetic/modulo.hpp"

namespace algorithm {

namespace internal {

// return x mod m.
template <std::unsigned_integral Type>
constexpr std::uint32_t modulo(Type x, std::uint32_t mod) { return x % mod; }

// return x mod m.
template <std::unsigned_integral Type>
constexpr std::uint32_t modulo(Type x, std::int32_t mod) { return modulo(x, static_cast<std::uint32_t>(mod)); }

// return x mod m.
template <std::signed_integral Type>
constexpr std::uint32_t modulo(Type x, std::uint32_t mod) {
    x %= static_cast<std::int64_t>(mod);
    if(x < 0) x += static_cast<std::int64_t>(mod);
    return x;
}

// return x mod m.
template <std::signed_integral Type>
constexpr std::uint32_t modulo(Type x, std::int32_t mod) {
    x %= mod;
    if(x < 0) x += mod;
    return x;
}

}  // namespace internal

}  // namespace algorithm


#line 10 "algorithm/Math/ModularArithmetic/mod_inv.hpp"

namespace algorithm {

namespace internal {

// return pair of (x, g) s.t. g=gcd(a,m), ax=g (mod m), 0<=x<m/g.
constexpr std::pair<std::uint32_t, std::uint32_t> mod_inv(std::uint32_t a, std::uint32_t m) {
    if(a == 0) return {0, m};
    std::uint32_t s = m, t = a;
    std::uint32_t u = m, v = 1;
    while(true) {
        std::uint32_t q = s / t;
        s -= t * q, u -= v * q;
        if(s == 0) return {v, t};
        q = t / s;
        t -= s * q, v += (m - u) * q;
        if(t == 0) return {u, s};
    }
}

}  // namespace internal

// モジュラ逆数（乗法逆元）．
// a^-1 mod m を求める．解が存在する必要十分条件は，aとmが互いに素であること．O(log a).
template <std::integral Type>
constexpr std::int64_t mod_inv(Type a, std::int32_t m) {
    assert(m >= 1);
    auto [x, g] = internal::mod_inv(::algorithm::internal::modulo(a, m), m);
    assert(g == 1);
    return x;
}

}  // namespace algorithm


#line 8 "algorithm/Math/Combinatorics/naive_combination.hpp"

namespace algorithm {

// 順列．O(K).
constexpr long long nPk(long long n, long long k) {
    assert(n >= 0);
    assert(k >= 0);
    if(n < k) return 0;
    long long res = 1;
    for(long long i = 0; i < k; ++i) res *= (n - i);
    return res;
}

// 順列（mod付き）．O(K).
constexpr long long nPk(long long n, long long k, int mod) {
    assert(n >= 0);
    assert(k >= 0);
    assert(mod >= 1);
    if(n < k) return 0;
    n %= mod;
    long long res = 1 % mod;
    for(long long i = 0; i < k; ++i) {
        long long tmp = n - i;
        if(tmp < 0) tmp += mod;
        res = res * tmp % mod;
    }
    return res;
}

// 組合せ．O(min(K,N-K)).
constexpr long long nCk(long long n, long long k) {
    assert(n >= 0);
    assert(k >= 0);
    if(n < k) return 0;
    k = std::min(k, n - k);
    long long res = 1;
    for(long long i = 0; i < k; ++i) res = res * (n - i) / (i + 1);
    return res;
}

// 組合せ（mod付き）．
constexpr long long nCk(long long n, long long k, int mod) {
    assert(n >= 0);
    assert(k >= 0);
    assert(mod >= 1);
    if(n < k) return 0;
    k = std::min(k, n - k);
    return nPk(n, k, mod) * mod_inv(nPk(k, k, mod), mod) % mod;
}

// 重複組合せ．O(min(N-1,K)).
constexpr long long nHk(long long n, long long k) {
    assert(n >= 0);
    assert(k >= 0);
    if(k == 0) return 1;
    if(n == 0) return 0;
    return nCk(k + n - 1, k);
}

// 重複組合せ（mod付き）．
constexpr long long nHk(long long n, long long k, int mod) {
    assert(n >= 0);
    assert(k >= 0);
    assert(mod >= 1);
    if(k == 0) return 1 % mod;
    if(n == 0) return 0;
    return nCk(k + n - 1, k, mod);
}

}  // namespace algorithm

Back to top page