組み合わせ nCk
(library/number/combination.hpp)

• View this file on GitHub
• Last update: 2026-01-07 21:05:45+09:00
• Include: #include "library/number/combination.hpp"

組み合わせ nCk

できること

• $nCk$ を求める

計算量

$O(k)$

使い方

long long comb = combination(n, k);

Verified with

• 組み合わせ nCkのテスト (tests/number.combination.test.cpp)

Code

#pragma once
long long combination(int n, int k) {
    if (k < 0 || n < k) return 0ll;
    long long res = 1;
    for (int i = 1; i <= k; ++i) {
        res *= n--;
        res /= i;
    }
    return res;
}

#line 2 "library/number/combination.hpp"
long long combination(int n, int k) {
    if (k < 0 || n < k) return 0ll;
    long long res = 1;
    for (int i = 1; i <= k; ++i) {
        res *= n--;
        res /= i;
    }
    return res;
}

Back to top page