[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; } }
関連問題
- 大ジャンプ (ABC011)
組み合わせに関する公式
二項定理
式変形により色々導き出せます。
その他
関連するABCの問題
- Blue and Red Balls (ABC132)
- Knight (ABC145) … パスカルの三角形を意識してみましょう
- Many Many Paths (ABC154)
- Roaming (ABC156)
- 11 (ABC066)
- Maximum Average Sets (ABC057)
重複組み合わせ
同じものをいくつでも選んで良いときの組み合わせ数
その他
同じモノが有限個ある時の組み合わせ数
文字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; });
(参考)
関連問題
- March (ABC089)
順列
完全順列(撹乱順列)
1,2,⋯,n を並び替えてできる順列のうち,全てのiに対してAi != iである数列
この順列の個数$a_n$は以下の式で表せる
完全順列の個数$a_n$のことをモンモール数という。
この式は包除原理によって導出することが出来る。
(参考)
関連問題
その他
- (Bullet) (ABC168)
禁止ペアがある時の組み合わせ