▲「お兄ちゃん、この前 $\bmod$ について教えてもらったやつの続きの話、聞いてもいい？」
■「うん。僕が作ってる、$\bmod$ 上での階乗・階乗逆元を事前計算するクラスを紹介するよ」
O(n) での逆元列挙
■「今回は法が素数の場合だけを考えるから、法を $P$ としておこう。常に $\bmod P$ で考える。法が合成数だと、階乗の逆元が計算できないからね」
▲「この前言ってたけど、$n$ 以下の正整数の逆元を $O(n)$ で列挙できるんだっけ？」
■「うん」
▲「それって、 1 つの正整数の逆元を $O(1)$ で計算できるってこと？」
■「いや、そうではないよ。 1 つの正整数の逆元を計算するだけなら、$O(\log P)$ 」
▲「じゃあどういうこと？」
■「$n$ 以下の正整数の逆元を計算するときに、$1$ から順番に計算していくんだ」
▲「うん」
■「だから、$k^{-1}$ を計算するとき、$k$ 未満の正整数の逆元はすでに知っている」
▲「あー、$k^{-1}$ の計算に、すでに知ってる逆元を利用すると $O(1)$ で計算できるってこと？」
■「そういうこと。だから、1 個だけのための計算を $n$ 回やるよりも高速にできる」
▲「それで、どうやるの？」
■「問題設定を確認しよう。今知りたいのは、素数 $P$ を法とした剰余の世界での掛け算に対する、整数 $i$ の逆元 $i^{-1}$ だ」
▲「$i$ って虚数？」
■「いやいや、整数だよ。後で for ループを回すから $i$ が自然かなと思って」
▲「そっか。なんで虚数単位に $i$ なんて平凡な記号つけちゃったんだろうねー」
■「それは知らないけど、とにかく、この式を満たす整数 $x$ を知りたいということ」
$$ix\equiv 1\pmod{P}$$
▲「そうだね。これを $O(1)$ で見つけるってできるのかな」
■「まず、『とりあえず好きに決めた値 $y$ でやってみて、ダメだったら帳尻合わせをする』というテクニックを使う」
▲「そんなテクニックあるの？」
■「競プロでもたまに使えるよ。一旦決め打ちしてから帳尻合わせ」
▲「で、今回の場合はどうなるの？」
■「好きな整数を 1 つ選んで、$iy$ を計算したとする。もちろん $iy$ を $P$ で割った余りが $1$ になるとは限らないから、余りを $r$ をおこう」
$$iy=r\pmod{M}$$
▲「なんか無関係な文字が 2 つも出てきちゃって、よけいに複雑になってない？」
■「大丈夫大丈夫。上の式から $i^{-1}$ が得られるとしたら、どうやって計算すればいいと思う？」
▲「何その質問。難しすぎない？」
■「まあ考えてみてよ」
▲「うーん。さっき言ってたのが、$i$ 未満の数についての逆元はすでに知ってるってことだから、それを使うはずだよね」
■「うんうん」
▲「$y$ の逆元は知ってても関係なさそうかな。じゃあ、$r$ の逆元を知ってたらどうだろう…… なんかいけそう！」
■「$r^{-1}$ を知っているとしたらどうなる？」
▲「$r^{-1}$ を知ってたら、両辺に $r^{-1}$ を掛けて、こうなるね」
$$iyr^{-1}\equiv rr^{-1}\equiv 1\pmod{P}$$
■「ということは？」
▲「ということは、$yr^{-1}$ が $i$ の逆元だ！」
■「そういうこと。それが帳尻合わせ」
▲「なるほどー、かっこいいね、この解き方」
■「でもまだ問題がある」
▲「$r$ の逆元を知ってたらいいけど、まだ計算してない値だったらダメってことだよね」
■「うん。つまり、$r$ についてどういう条件が成り立っていてほしい？」
▲「$i$ 未満の整数については逆元が計算済みだから、$r<i$ であれば良いし、そうじゃなかったらダメってことだよね」
■「うん。その条件を満たすような $y$ を探したいね」
▲「そうだねー」
■「はい。どうぞ」
▲「え、これも放り投げられるの」
■「今日はね、僕は何もしたくないんだ」
▲「ひどい！」
■「じゃあ、どうぞ」
▲「やるしかないか…… $iy$ を $P$ で割った余りが $i$ より小さくなれば良いってことだから、$y=1$ じゃダメだよね」
■「そうだね。$y=1$ だと $r=(i\times 1)\bmod P=i$ だ」
▲「だから、$y$ を増やしていって、初めて $P$ を超えた瞬間とかだと、余りは $i$ より小さいっぽい？」
■「ぽいね」
▲「こういうこと！ $P$ を超えた瞬間だと、$iy-P$ が $i$ より大きいことはありえないはず！ もしそうだったらその一つ手前の $i(y-1)$ の時点で $P$ を超えてるから！」
■「そうだね。この図の場合は $y=4$ ってことだね。$P$ が素数だから、$iy$ が $P$ の倍数になることはあり得ないっていうのもポイントだね」
▲「うん」
■「じゃあ、この $y$ と $r$ はどうやって計算できる？」
▲「えっと、$y$ は $P$ を $i$ で割ったときの切り上げの整数で、$r$ はそのまま $iy$ を $P$ で割った余りで計算できるはず！」
■「今回、$P$ は必ず $i$ の倍数じゃないから、プログラムとしては y=P/i+1 と書けるね」
▲「うん。切り捨てて +1 だね」
■「じゃあ、これで本当に逆元が計算できることを証明しよう」
▲「切り捨てとか切り上げとかってどうするの？」
■「$P$ を $i$ で割った商と余りを $a,b$ とするのが楽かな。つまり、$P=ai+b$ で、$P$ が素数だから $0<b<i$」
▲「そのときは、$y=a+1$ で、$r=i(a+1)\bmod P$？」
■「$r$ も変形して $\bmod$ が無い形にしたいな」
▲「$r=ai+i=(P-b)+i\equiv i-b$ ってこと？」
■「だね。実際、$0<b<i$ だから、$0<i-b<i$ になる」
▲「で、$i$ の逆元であって欲しい $x$ は $yr^{-1}$ だから $x=(a+1)(i-b)^{-1}$ かな」
■「うん」
▲「これが逆元になってるか確かめるために、$ix$ を計算してみれば良いんだね。こうなって……」
$$ix=i(a+1)(i-b)^{-1}=(ai+i)(i-b)^{-1}$$
▲「$P=ai+b$ だから $ai=P-b$ で……」
$$ix=(P-b+i)(i-b)^{-1}\equiv (i-b)(i-b)^{-1}\equiv 1$$
▲「できたー！」
■「うん。ちゃんと逆元になっているね」
▲「なんかややこしいね」
■「もうちょっとシンプルにする方法があるよ」
▲「シンプルにって、どうやって？」
■「さっきの図を使うと、こんな感じ。ここで、$y=a$ とする。そして、$r=-b$ とする」
▲「$P$ を超えた瞬間じゃなくて、超える直前ってこと？ でも、$-b$ の逆元ってどうなるの？」
■「それは簡単。$b^{-1}$ に $-1$ を掛けたものになる。なぜなら、$-1$ の逆元は必ず $-1$ だから」
$$(-b)^{-1}=(-1)^{-1}b^{-1}=-b^{-1}$$
▲「$(-1)\times(-1)=1$ だから、そりゃそうか。あと、積の逆元は逆元の積になるんだね。負の数になったら $P$ から引けばいいってこと？」
■「うん」
▲「じゃあ、$P=ai+b, y=a, r=-b$ だから、$x=-ab^{-1}$ になるんだよね。で、実際に $ix$ を計算すると……」
$$ix=i(-ab^{-1})=-iab^{-1}=-(P-b)b^{-1}\equiv bb^{-1}\equiv 1$$
▲「ちゃんと $1$ になった！」
■「こっちの方がプログラムで書くにはシンプルで良いかなと思うよ。$ab^{-1}$ が $P$ より大きくなる可能性があるから、$ab^{-1}$ を計算した時点で $\bmod P$ をとっておくことに注意してね」
逆元列挙のプログラム
▲「inverse[i] に $i$ の逆元が入ってるとしたら、計算式はこう？」
|
1 |
inverse[i] = mod - ((mod / i) * inverse[mod % i] % mod); |
■「そうだね。mod が法 $P$ のことだね。$P=ai+b$ のとき、mod / i が $a$、mod % i が $b$ を表しているね」
▲「じゃあ、inverse[1]=1 を事前に代入しておいてから、これをループで回せば計算できる？」
■「うん。それで大丈夫」
▲「全体はこう？」
|
1 2 3 4 5 6 7 8 9 10 |
// n 以下の正整数の mod 逆元を列挙 vector<long long> calc_inverse(int n, int mod) { vector<long long> inverse(n + 1); // inverse[n] まで欲しいのでサイズは n+1 inverse[0] = 0; // 0 の逆元は無いので適当に埋める inverse[1] = 1; // 1 の逆元は必ず 1 for (int i = 2; i <= n; i++) { inverse[i] = mod - ((mod / i) * inverse[mod % i] % mod); } return inverse } |
■「良いね。最終的にクラスを作るから結果を格納する配列 inverse はクラスのメンバになるけどね」
▲「クラスのことはあんまり知らないけど、まあいいや。階乗の計算は普通に前から掛けていくだけだよね？」
■「うん」
▲「階乗って英語で何ていうの？」
■「”factorial” だよ」
▲「じゃあ、こうだね」
|
1 2 3 4 5 6 7 8 9 |
// n! を mod で割った余りを計算 vector<long long> calc_factorial(int n, int mod) { vector<long long> factorial(n + 1); factorial[0] = 1; // 0 の階乗は 1 for (int i = 1; i <= n; i++) { factorial[i] = (factorial[i - 1] * i) % mod; } return factorial; } |
■「その調子で、階乗の逆元も作っちゃおう」
▲「階乗の逆元は、逆元を階乗していけばいいの？」
■「そうだね。$(ab)^{-1}=a^{-1}b^{-1}$ だから」
$$n!^{-1}\equiv 1^{-1}\times 2^{-1}\times 3^{-1}\times\dots\times n^{-1}$$
▲「これでどうだ！」
|
1 2 3 4 5 6 7 8 9 |
// i! の mod 逆元を計算 void calc_factorial_inverse(int n, int mod) { vector<long long> factorial_inverse(n + 1); factorial_inverse[0] = 1; // 0 の階乗は 1 なのでその逆元は 1 for (int i = 1; i <= n; i++) { factorial_inverse[i] = (factorial_inverse[i - 1] * inverse[i]) % mod; } return factorial_inverse; } |
■「正解。じゃあ、これらを組み合わせてクラスを作る」
▲「よく知らないけどやってみよー！」
階乗逆元計算クラス
■「FactorialMod というクラスを作ろう。大枠はこうなる」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// 階乗・組み合わせの mod 逆数 class FactorialMod { int max_num; // 扱う最大の値 int mod; // mod の法（素数） vector<long long> inverse; // 逆元 vector<long long> factorial; // 階乗 vector<long long> factorial_inverse; // 階乗の逆元 // コンストラクタ FactorialMod(int _max_num, int _mod) { // 配列を初期化してそれぞれの値を計算する処理を書く } }; |
▲「コンストラクタっていうのは、初期化するやつだよね」
■「うん。正確には、そのクラスの変数を作る（インスタンス化する）ときに実行される処理だね。必ず public で、返り値は無い」
▲「public: っていうのは？」
■「public: より下の行に書いた変数・関数をすべて public にするという記号。public というのは、外部から直接アクセスできるということね」
▲「じゃあ、そのコンストラクタの中で、vector のサイズを確保して、逆元とかの計算をすればいいってこと？」
■「うん。面倒だから完成形をいきなり書いちゃうけど、こうなる」
※ 簡単にするためメンバ初期化子リストを使用していません
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// 階乗・組み合わせの mod 逆数 class FactorialMod { // 逆元を計算 void calc_inverse() { inverse[0] = 0; inverse[1] = 1; for (int i = 2; i <= max_num; i++) { inverse[i] = mod - ((mod / i) * inverse[mod % i] % mod); } } // i! を mod で割った余りと逆元を計算 void calc_factorial_inverse() { factorial[0] = factorial_inverse[0] = 1; for (int i = 1; i <= max_num; i++) { factorial[i] = (factorial[i - 1] * i) % mod; factorial_inverse[i] = (factorial_inverse[i - 1] * inverse[i]) % mod; } } public: int max_num; // 扱う最大の値 int mod; // mod の法（素数） vector<long long> inverse; // 逆元 vector<long long> factorial; // 階乗 vector<long long> factorial_inverse; // 階乗の逆元 FactorialMod(int _max_num, int _mod) { max_num = _max_num; mod = _mod; inverse = vector<long long>(max_num + 1); factorial = vector<long long>(max_num + 1); factorial_inverse = vector<long long>(max_num + 1); calc_inverse(); calc_factorial_inverse(); } }; |
▲「calc_inverse と calc_factorial_inverse がそれぞれ逆元を計算する関数で、コンストラクタの中でそれを実行してるってこと？」
■「その通り。使うときは、FactorialMod 型の変数を用意して、その変数にピリオドをつけてメンバ変数にアクセスする」
▲「メンバ変数っていうのが、inverse とかのこと？」
■「うん。使用例はこんな感じ」
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int main(void){ int MOD = 1000000007; int MAX_NUM = 100; FactorialMod factorial_mod(MAX_NUM, MOD); // ここでコンストラクタが実行される cout << factorial_mod.inverse[10] << endl; // 10 の逆元 mod 1000000007 cout << factorial_mod.factorial[10] << endl; // 10! mod 1000000007 cout << factorial_mod.factorial_inverse[10] << endl; // 10! の逆元 mod 1000000007 return 0; } |
▲「簡単だね」
■「ちなみに、calc_inverse 関数は public じゃないから、factorial_mod.calc_inverse(); みたいにクラスの外から実行しようとするとエラーになる」
▲「隠す必要ある？」
■「まあ、このぐらいの規模なら無いんだけどね。もっと複雑なクラスになると、隠しておいた方がコーディングしやすくなることもある」
▲「ふーん」
■「じゃあ、今度はこのクラスに組合せの計算をする関数を追加しよう」
組合せの計算
▲「この前言ってたやつだよね。組合せがこの式で計算できるから、」
$${}_n\mathrm{C}_k=\frac{n!}{k!(n-k)!}$$
▲「逆元を使って、こうすればいいんだよね」
$${}_n\mathrm{C}_k=n!\times k!^{-1}\times (n-k)!^{-1}$$
■「そう。じゃあ、書いてみて」
▲「さっきのコードに？ 書けるかな…… えっと、関数名はどうしよう」
■「combination_mod とかでいいんじゃない？」
▲「引数は、$n$ と $k$ だよね。で、返り値は long long にしておけばいいかな」
■「そうだね」
▲「factorial_mod.combination_mod(n, k) っていうふうに使うの？」
■「うん」
▲「じゃあ、public にすればいいんだよね。てことは…… こう？」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// 階乗・組み合わせの mod 逆数 class FactorialMod { // 略 public: int max_num; // 扱う最大の値 int mod; // mod の法（素数） vector<long long> inverse; // 逆元 vector<long long> factorial; // 階乗 vector<long long> factorial_inverse; // 階乗の逆元 FactorialMod(int _max_num, int _mod) { max_num = _max_num; mod = _mod; inverse = vector<long long>(max_num + 1); factorial = vector<long long>(max_num + 1); factorial_inverse = vector<long long>(max_num + 1); calc_inverse(); calc_factorial_inverse(); } // nCk を mod で割った余りを計算 long long combination_mod(int n, int k) { return (((factorial[n] * factorial_inverse[k]) % mod) * factorial_inverse[n - k]) % mod; } }; |
■「そうだね。一応、範囲外の値が来たときの対処を用意しておいた方がいいかな」
▲「$n, k$ が範囲外の値だったり $k>n$ だったりの場合は、そんな選び方は無いから $0$ を返しておけばいい？」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// 階乗・組み合わせの mod 逆数 class FactorialMod { // 略 public: int max_num; // 扱う最大の値 int mod; // mod の法（素数） vector<long long> inverse; // 逆元 vector<long long> factorial; // 階乗 vector<long long> factorial_inverse; // 階乗の逆元 FactorialMod(int _max_num, int _mod) { max_num = _max_num; mod = _mod; inverse = vector<long long>(max_num + 1); factorial = vector<long long>(max_num + 1); factorial_inverse = vector<long long>(max_num + 1); calc_inverse(); calc_factorial_inverse(); } // nCk を mod で割った余りを計算 long long combination_mod(int n, int k) { if (n < 0 || k < 0 || n > max_num || k > max_num || k > n) return 0; return (((factorial[n] * factorial_inverse[k]) % mod) * factorial_inverse[n - k]) % mod; } }; |
■「まあ、それでいいんじゃないかな。入力の範囲について assert するのでも良いと思うけど、とりあえずは難しいことは考えないことにしよう」
▲「じゃあその assert どうこうっていうのは時が来たら教えてね」
重複組合せ
■「ついでに、重複組合せも実装してみようか」
▲「重複組合せって、丸と線のやつ？」
■「気持ちは分かるけどその覚え方は変だよ」
▲「どんな問題だっけ」
■「互いに区別できない $k$ 個の球があって、これらを互いに区別できる $n$ 個の箱に入れるときに、入れ方は何通りあるか、とか」
▲「変な問題だね」
■「シンプルにした結果、謎の問題設定になっているだけで、汎用性は高いよ」
▲「球が区別できないから、最終的に『球が箱 $1$ に何個、箱 $2$ に何個、……、箱 $k$ に何個』っていう状態になって、この数列が何通りできるか？ってことだよね」
■「うん。だから、和が $k$ になるような、$0$ 以上の整数 $n$ 個の選び方は何通り？ とも言える」
▲「$x_1+x_2+\dots x_n=k$ で、すべての $i$ に対して $x_i>0$ ってことだよね」
■「そうだね。ちなみに、$x_i>a_i$ として、下限値が $0$ 以外で設定されている場合は、$y_i=x_i-a_i$ とした新しい変数 $y_i$ を用意して、和の条件の両辺から $a_i$ を全部引くと同じ問題に変形できるよ」
▲「なんで重複組合せっていうの？」
■「$n$ 種類の箱などの中から $k$ 個選ぶんだけど、$k$ 個の中で重複があっても良いから、重複組合せ。『$n$ 個の選択肢から重複を許して $k$ 個選ぶ方法の数』ということ」
▲「りんご、梨、みかんがたくさん売ってて、果物を $10$ 個買うときの買い方、みたいなこと？」
■「そうそう。色んな表現方法がある。この重複組合せの答えの値を、${}_n\mathrm{H}_k$ と書く」
▲「なんで $\mathrm{H}$ ？」
■「以前調べたことがあるんだけど、斉次多項式 Homogeneous polynominal の頭文字らしいよ」
▲「斉次多項式？」
■「斉次というのは、字数が揃っているということ。例えば、$(x+y+z)^2$ を展開すると、$x^2+y^2+z^2+2xy+2yz+2zx$ となって、$6$ つの項が出てくる。この $6$ は、$3$ つの変数から重複を許して $2$ つ選ぶ方法の数 ${}_3\mathrm{H}_2$ になっている」
▲「思わぬところから来たね」
■「で、この ${}_n\mathrm{H}_k$ の値は、コンビネーションで表現できる」
▲「丸と線のやつだ！」
■「そうだね。詳しい説明は調べてほしいけど、$n$ 種類の選択肢から重複を許して $k$ 個選ぶ方法は、丸を $k$ 個、仕切り線を $n-1$ 個用意して、好きな順に並べる並べ方に一対一対応する」
▲「りんご、梨、みかんの $3$ 種類の果物が売ってあるお店で、果物を $10$ 個買うときは、${}_3\mathrm{H}_{10}$ だから、丸を $10$ 個と仕切り線を $3-1=2$ 本並べて、こうなるってことだよね」
■「そうそう。${}_n\mathrm{H}_k$ は、$(n-1)+k$ 箇所の場所から丸を $k$ 個置く場所を選ぶ方法の数と一致するから、以下の式が成り立つ」
$${}_n\mathrm{H}_k={}_{n+k-1}\mathrm{C}_k$$
▲「そのままコードで書けそうだね」
■「じゃあ、重複組合せを実装してみよう」
▲「関数名は？」
■「そのまま英訳すると長くなるけど、Wikipedia に “multi-choose” と書いてあったから、これを使おう」
▲「じゃあ、こうだね」
|
1 2 3 4 |
// nHk を mod で割った余りを計算 long long multi_choose_mod(int n, int k) { return combination_mod(n + k - 1, k); } |
■「そのまんまだね」
▲「範囲外の処理は combination_mod がやっているから書かなくても大丈夫だよね？」
■「そうだね。使うときの注意としては、$n\le 10^6,k\le 10^6$ であっても、$n+k-1$ は $2\times 10^6-1$ になりうるので、FactorialMod factorial_mod(2000000); で変数を作らないといけないところだね」
▲「あー、たしかに。うっかりしそう」
AOJ で確認
■「Aizu Online Judge (AOJ) というオンラインジャッジのサイトに、このあたりのコードを確認できる問題があるから使おう。まずはこれ」
$n$ 個の区別できるボールを $k$ 個の区別できる箱に入れるとき、可能な入れ方の総数を $10^9+7$ で割った余りを求めてください。
$1\le n\le 1000$
$1\le k\le 1000$
▲「これは、両方区別できるから $k$ 種類の選択が $n$ 回あるだけで、$k^n$ ってことだよね？」
■「うん」
▲「じゃあ、こうだね」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <iostream> #include <vector> using namespace std; // n の k 乗を mod で割った余りを計算 long long power_mod(long long n, long long k, long long mod) { long long result = 1; // k を右シフトしつつ n を 2 乗していく while (k > 0) { // k の最下ビットが 1 なら、今の n を答えに掛ける if ((k & 1) == 1) result = (result * n) % mod; n = n * n % mod; k >>= 1; } return result; } // 階乗・組み合わせの mod 逆数 class FactorialMod { // 逆元を計算 void calc_inverse() { inverse[0] = 0; inverse[1] = 1; for (int i = 2; i <= max_num; i++) { inverse[i] = mod - ((mod / i) * inverse[mod % i] % mod); } } // i! を mod で割った余りと逆元を計算 void calc_factorial_inverse() { factorial[0] = factorial_inverse[0] = 1; for (int i = 1; i <= max_num; i++) { factorial[i] = (factorial[i - 1] * i) % mod; factorial_inverse[i] = (factorial_inverse[i - 1] * inverse[i]) % mod; } } public: int max_num; // 扱う最大の値 int mod; // mod の法（素数） vector<long long> inverse; // 逆元 vector<long long> factorial; // 階乗 vector<long long> factorial_inverse; // 階乗の逆元 FactorialMod(int _max_num, int _mod) { max_num = _max_num; mod = _mod; inverse = vector<long long>(max_num + 1); factorial = vector<long long>(max_num + 1); factorial_inverse = vector<long long>(max_num + 1); calc_inverse(); calc_factorial_inverse(); } // nCk を mod で割った余りを計算 long long combination_mod(int n, int k) { if (n < 0 || k < 0 || n > max_num || k > max_num || k > n) return 0; return (((factorial[n] * factorial_inverse[k]) % mod) * factorial_inverse[n - k]) % mod; } // nHk を mod で割った余りを計算 long long multi_choose_mod(int n, int k) { return combination_mod(n + k - 1, k); } }; const int MOD = 1000000007; int main(void) { int n, k; cin >> n >> k; cout << power_mod(k, n, MOD) << endl; return 0; } |
■「そうだね。じゃあ次はこれ」
$n$ 個の区別できるボールを $k$ 個の区別できる箱に入れるとき、可能な入れ方の総数を $10^9+7$ で割った余りを求めてください。
ただし、各箱に入れることのできるボールの数は高々 $1$ つまでです。
$1\le n\le 1000$
$1\le k\le 1000$
▲「箱に $1$ つしかボールを入れられないってことは、順列ってことだよね？」
■「そうだね。${}_k\mathrm{P}_n$ だ」
▲「じゃあ、逆元を使ってこう書けるね。$n$ と $k$ が思ってるのと逆でややこしい」
$${}_k\mathrm{P}_n=\frac{k!}{(k-n)!}\equiv k!\times (k-n)!^{-1}$$
■「コードを書いてみよう」
▲「こうかな？」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// 略 const int MOD = 1000000007; int main(void) { int n, k; cin >> n >> k; FactorialMod factorial_mod(1000, MOD); if (k < n) { cout << 0 << endl; } else { cout << factorial_mod.factorial[k] * factorial_mod.factorial_inverse[k - n] % MOD << endl; } return 0; } |
■「正解。じゃあ次」
$n$ 個の区別できないボールを $k$ 個の区別できる箱に入れるとき、可能な入れ方の総数を $10^9+7$ で割った余りを求めてください。
ただし、各箱に入れることのできるボールの数は高々 $1$ つまでです。
$1\le n\le 1000$
$1\le k\le 1000$
▲「ボールの区別ができなくなったから、$k$ 個の箱のうち $n$ 個にボールが入ってるっていう状態になるだけだね。ってことは組合せ？」
■「書いてみよう」
▲「テンポが良いね。${}_k\mathrm{C}_n$ だから、こうだね」
|
1 2 3 4 5 6 7 8 9 10 |
// 略 const int MOD = 1000000007; int main(void) { int n, k; cin >> n >> k; FactorialMod factorial_mod(1000, MOD); cout << factorial_mod.combination_mod(k, n) << endl; return 0; } |
■「正解。じゃあ最後」
$n$ 個の区別できないボールを $k$ 個の区別できる箱に入れるとき、可能な入れ方の総数を $10^9+7$ で割った余りを求めてください。
$1\le n\le 1000$
$1\le k\le 1000$
▲「箱の個数制限が無くなったから、$k$ 種類の選択肢から重複を許して $n$ 個選ぶ、${}_k\mathrm{H}_n$ だね」
■「どうぞ」
▲「こうだ！」
|
1 2 3 4 5 6 7 8 9 10 |
// 略 const int MOD = 1000000007; int main(void) { int n, k; cin >> n >> k; FactorialMod factorial_mod(1000, MOD); cout << factorial_mod.multi_choose_mod(k, n) << endl; return 0; } |
■「あれ忘れてるよ」
▲「あれ？ あ！ 重複組合せだから、階乗の計算する数を $n+k-1$ までにしないとダメなんだったね。これで大丈夫？」
|
1 2 3 4 5 6 7 8 9 10 |
// 略 const int MOD = 1000000007; int main(void) { int n, k; cin >> n >> k; FactorialMod factorial_mod(1999, MOD); cout << factorial_mod.multi_choose_mod(k, n) << endl; return 0; } |
■「正解。$-1$ は面倒だから $2000$ までにしてもいいけどね」
▲「やったー！ 組合せをマスターしたぞー！ 疲れた！」
■「お疲れ様。AOJ のボールと箱の問題は 12 問あるから、残りは勝手にやっといてね」
▲「えぇ……」