組み合わせ

[latexpage]

Contents

Combination

nCkは上記式で求めることが可能です。

分母の階乗要素と分子の階乗要素(の逆元)を予め求めてテーブル化しておくことにより、高速に計算が可能となります。

実装

ModInt構造体を用いて実装します。
ModInt構造体のコードについては下記ページから別途コピーする必要があります。

剰余の世界での四則演算

template <typename T>
class Combination {
 public:
  Combination(ll _max_n) : max_n(_max_n), factional(max_n + 1), inv(max_n + 1) {
    factional[0] = 1;
    inv[0] = 1;
    for (ll i = 0; i < max_n; i++) {
      factional[i + 1] = factional[i] * (i + 1); // n!(mod M)
      inv[i + 1] = inv[i] / (i + 1);             // k!^(M-2) (mod M)
    }
  }

  // nCk
  T choose(ll n, ll k) {
    if (n == 0 && k == 0)
      return 1;
    if (n < k || n < 0)
      return 0;
    T tmp = inv[n - k] * inv[k];
    return tmp * factional[n];
  }

 private:
  const ll max_n;
  std::vector<T> factional;
  std::vector<T> inv;
};

#define mod (ll)(1e9 + 7)
using mint = ModInt<mod>;
using Comb = Combination<mint>;

(参考)

パスカルの三角形による実装

nの値が小さければ、「パスカルの三角形」によっても求めることが可能です。
n<=5000程度が限界ですが、以下のような場合に使えます。

  • modintではない値を求める場合
  • その選び方をされる確率の計算

はこちらの方法を使うのが良いでしょう。

void init_comb(vvll& comb, int n) {
  comb.resize(n + 1);
  fill(all(comb), vll(n + 1));

  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= i; j++) {
      if (j == 0 || j == i) {
        comb[i][j] = 1;
      } else {
        comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
      }
    }
  }
}
// using vld = vector<ld>;
// using vvld = vector<vld>;

void init_prob(vvld& prob, int n) {
  prob.resize(n + 1);
  fill(all(prob), vld(n + 1));

  prob[0][0] = 1;

  for (int i = 1; i <= n; i++) {
    prob[i][0] = prob[i - 1][0] / 2;
    for (int j = 1; j < i; j++) {
      prob[i][j] = prob[i - 1][j - 1] + prob[i - 1][j];
      prob[i][j] /= 2;
    }
    prob[i][i] = prob[i - 1][i - 1] / 2;
  }
}

 

関連問題

組み合わせに関する公式

二項定理

式変形により色々導き出せます。

その他

関連するABCの問題

重複組み合わせ

同じものをいくつでも選んで良いときの組み合わせ数

その他

同じモノが有限個ある時の組み合わせ数

文字xを $p$ 個，文字yを $q$ 個使って出来る文字列は何通りあるか？

x及びyすべてを区別出来ると考えた時、全体の並べ方は$(p+q)!$通りです。
そこからxの並べ方の種類$p!$とyの並べ方の種類$q!$を割れば、区別しない場合の並べ方のパターン数になります。

参考

組み合わせの全列挙

DFSで実装できます。

// [0 n)からk個選ぶで組み合わせを列挙し、関数fを実行する
void comb_dfs(vll &indexes, int n, int k, std::function<void(const vll &)> f) {
  if (k == 0) {
    f(indexes);
    return;
  }
  // 選ぶ数字が足りない時
  if (n < k) {
    return;
  }

  // 現在対象の値を選ばない場合
  comb_dfs(indexes, n - 1, k, f);
  // 現在対象の値を選ぶ場合
  indexes[k - 1] = n - 1; // 1-indexedにしたい場合は-1を削除
  comb_dfs(indexes, n - 1, k - 1, f);
}

// nCkの組み合わせに対して処理を実行する
void foreach_comb(int n, int k, std::function<void(const vll &)> f) {
  vll indexes(k);
  comb_dfs(indexes, n, k, f);
}

使い方

ll n = 5;
ll k = 3;
foreach_comb(n, k, [&](const vll &indexes) {
  for (const auto &i : indexes) {
    cout << i << " ";
  }
  cout << endl;
});

 

(参考)

関連問題

順列

完全順列(撹乱順列)

1,2,⋯,n を並び替えてできる順列のうち，全てのiに対してAi != iである数列

この順列の個数$a_n$は以下の式で表せる

完全順列の個数$a_n$のことをモンモール数という。

この式は包除原理によって導出することが出来る。

(参考)

関連問題

その他

  • (Bullet) (ABC168)
    禁止ペアがある時の組み合わせ