この問題は，模擬試験２の 5 番と同様に，20 点を取るためには数学的センスが必要な問題である．IOI の本番の問題を解くためには，高いプログラミングの技能が必要なことは言うまでもないが，数学的な思考力（特に，組合せや確率についての知識）も必須である．また，試験の解答に当たって，解を予測するためにシミュレーションを行なうことの必要性や有効性を知ってもらいたいという趣旨も込めて出題した．
　しかし、プログラミング技能だけに頼った力ずくでも 3 つの入力ファイルに対しては答えが求められるように，また，上述のような解の予測により 4 つ目の入力ファイルに対しても答えが求められるように入力データを作ったので，はじめに，その方法について述べよう．

　nk 枚のカードの配り方は全部で (nk) ! 通りあるから，これらすべての場合（ (nk) ! 通りの順列）を生成して，実際にゲームを行えば確率は正確に求めることができる．順列すべてを生成する方法はいろいろあるが，ここでは省略する． (nk) ! の値が 1000000 未満である n, k の値は以下の通りである．1000000 未満だと 1 秒以内で実行できる．

入力データのうち 2 つは，このような全数検査で答えが求められるものとした．

　さて，まず全数検査を行う簡単なプログラムを作って，いろんな n, k の値について確率を求めてみると，m = 0 なら k の値とは無関係に，求める確率が 1/n になるであろうことが推測できる（m = 1 の場合には，このような推測をすることはむずかしい）． 冒頭に書いたように，このようなことができる能力も実戦力として有効である．この推測ができれば，5 つの入力ファイルのうち 3 つまでは正しい答えが求められる．

　m = 1 の場合の答えを求めるには，数学的に確率を求めることが必要である．その確率は 1/n + 1/n (1 + 1/2 + ･･･ + 1/(n - 1)) である（証明は後述）． このような理論値が求められれば，あとは計算するだけであるが，小数第 10000 桁まで求めることを要求されているので，配列を用いた多倍長計算をするしかない．すなわち，配列要素 a[0], a[1], a[2], ..., a[10005] で小数

　　a[0] . a[1]a[2]･･･a[10005]

を表して（a[0] は整数部を，a[i] は小数第 i 位を表す： a[i] = 0, 1, 2, ..., 9），筆算で 1/n を計算したり桁数の多い足し算を計算したりするのと同様に計算する．つまり，模擬試験 2 の問題 5 と同様であるが，今回注意しなければならないのは，誤差の問題である．要求されているのは最大 10000 桁まで求めることであるが，やや多目の桁数を取って計算する必要がある．というのは，足し算を n 回行うので，末尾の桁における誤差（10000 回の足し算なら影響が 5 桁に及ぶ）の影響を排除するためである．なお，a[i] を 10 進 1 桁に限定しないほうが計算時間は短くなることに注意する．ただし，n = 10000 以下なら（この問題の入力データは n≦10000 としてある），そこまでしなくても時間がかからずに計算できる．

　最後に，カードをランダムに配ってゲームを 10000 回程度試行してみて，答えを予測するという手法も考えられるが，問題を作るに当たって実際に乱数を生成して試したところ，m = 0 の場合の解の推測はかろうじてできる可能性があるものの，m = 1 の場合は無理のようである．5 つの入力データのうちの 2 つは，このような方法でも求められるものとした．

　 2回目までに成功する確率が 1/n + 1/n (1 + 1/2 + 1/3 + … + 1/(n - 1)) であることの証明：
　どの山にどのような数（1 〜 n）が積まれているかではなく，順次山をたどる順番（すなわち，(1, 2, ..., n) × k の順列，がどうであるかが本質的なことである．1 回目の試行では，n 枚目が 1 (＝ 最初に引いた山の番号)であることが成功するための必要十分条件である（k 枚目の 1 が出るまでは，どの山も十分な枚数が残っている）． 最後に 1 が出現する確率は 1/n である（kn 枚目の数として 1 は k 通りの選び方があり，そのそれぞれについてそれ以外の k (n - 1) 枚はそれ以前に自由に現れてよいから，最後に 1 が来る場合の数は k (kn - 1) ! である．よって，最後に 1 が来る確率は k (kn - 1) ! / (kn) ! = 1/n である）． このように，k は確率に関与しない．
　さて，1 回目で失敗したとき，2 回目で成功する確率を考えよう．k = 1 の場合を考えれば十分である． 1 回目の試行で現れた数の順列が

　　 1 - - - … - - 　の場合には山が 1 つ無くなっていて，
　　 - 1 - - … - - 　の場合には山が 2 つ無くなっていて，
　　 - - 1 - … - - 　の場合には山が 3 つ無くなっていて，
　　・・・

といったようになることは明らかである．それぞれの場合は確率 1/n （1 が順列の特定の位置に来る確率）で起こる．しかも，山が i 個無くなっていた場合には（1≦i≦n - 1），そのあとで 2 回目の試行をしたときに成功する確率は 1/(n - i) である．これらの事象は排反独立であるから，2 回目に成功する確率 1/n (1 + 1/2 + … 1/(n - 1)) が得られる． 1 回目で成功する確率を加えて，2 回目までに成功する確率は 1/n + 1/n (1 + 1/2 + … 1/(n - 1)) である．