Combination - 二項係数
(lib/30-math/Combination.cpp)

• View this file on GitHub
• Last update: 2023-05-30 04:49:31+09:00

Combination

• 二項係数を返す

コンストラクタ

• Combination(int N)
  • binom(N,K)を愚直に前計算する

メソッド

• T binom(int n, int k)
  • 二項係数nCkを返す
  • $O(1)$
• T lucas(int n, int k, long long p)
  • ルーカスの定理によって、nCk mod pを返す。
  • コンストラクタで渡したNに対して、p <= Nである必要がある
  • n,kの値はなんでもよい。(p < n, p < kでもok）
  • $O(\log(n))$

参考資料

• C - ゲーマーじゃんけん
• B - 123 Triangle
• C - Tricolor Pyramid

Code

/*
 * @title Combination - 二項係数
 * @docs md/math/Combination.md
 */
template<class T> class Combination{
    vector<vector<T>> num;
public:
    //O(N^2)
    Combination(int N):num(N+1,vector<T>(N+1,(T)0)){
        num[0][0] = 1;
        for (int n = 1; n <= N; n++) {
            for (int k = 0; k <= n; k++) {
                num[n][k] = (num[n - 1][k]+(k?num[n - 1][k - 1]:0));
            }
        }
    }
    inline T binom(int n, int k) {
        return ((n < 0 || k < 0 || n < k) ? 0 : num[n][k]);
    }
    //nCk mod p (p is prime & p <= N)
    inline T lucas(int n, int k, long long p) {
        long long res=1;
        for(;n||k;n/=p,k/=p) (res *= num[n%p][k%p]) %= p;
        return res;
    }
};

#line 1 "lib/30-math/Combination.cpp"
/*
 * @title Combination - 二項係数
 * @docs md/math/Combination.md
 */
template<class T> class Combination{
    vector<vector<T>> num;
public:
    //O(N^2)
    Combination(int N):num(N+1,vector<T>(N+1,(T)0)){
        num[0][0] = 1;
        for (int n = 1; n <= N; n++) {
            for (int k = 0; k <= n; k++) {
                num[n][k] = (num[n - 1][k]+(k?num[n - 1][k - 1]:0));
            }
        }
    }
    inline T binom(int n, int k) {
        return ((n < 0 || k < 0 || n < k) ? 0 : num[n][k]);
    }
    //nCk mod p (p is prime & p <= N)
    inline T lucas(int n, int k, long long p) {
        long long res=1;
        for(;n||k;n/=p,k/=p) (res *= num[n%p][k%p]) %= p;
        return res;
    }
};

Back to top page