ABC021 D - 多重ループ

Change log
ae2eaea
9sako6
d669d36
9sako6
b35a12f
9sako6

#問題

#考察

問題を簡単にしてみます。1≤a1<a2<...<ak<n1 \leq a_1 < a_2 < ... < a_k < nを満たす組み合わせを考えます。11以上nn以下の整数をkk個選び、全て異なる整数であれば上記の条件を満たすように並べることができます（「並べ替えれば条件を満たせる」系の考え方だと思って慣れる）。つまり、11以上nn以下の整数をkk個選ぶ組み合わせに等しいです 。これはnCk{}_n C_kです。

本来は1≤a1≤a2≤...≤ak≤n1 \leq a_1 \leq a_2 \leq ... \leq a_k \leq nでした。これは、11以上nn以下の整数を重複を許してkk個選ぶ組み合わせに等しいです。

重複組み合わせを簡単に説明します。 重複組み合わせを理解するには仕切りを使った考え方が重要です。

桃太郎将軍は鬼退治のために軍隊を作りたいです。猿山、犬里、雉子ヶ谷にはそれぞれ、猿、犬、雉子が無限匹住んでいます。桃太郎将軍はこれらの土地から猿、犬、雉子を何匹かずつ雇って、軍隊を編成することにしました。しかし、きびだんごの在庫の問題で合計6匹までしか雇えません。桃太郎将軍は、軍隊を編成するメンバーの種類のパターンが何通りあるかを知りたいです。これを求めてください。ただし、雇わない種類が存在してもよいとします。

3種類の動物がいるので、2つの仕切りを使ってメンバーを3グループに分けてみます。

  • ○○|○○|○○
  • ○○|○|○○○
  • ○|○○○○|○
  • ○○○○○||○

例えば上記のような分け方があります。○で示したもののうち、左のグループから順に猿、犬、雉子になると決めます。

  • 猿猿|犬犬|鳥鳥
  • 猿猿|犬|鳥鳥鳥
  • 猿|犬犬犬犬|鳥
  • 猿猿猿猿猿||鳥

この「6つの○」と「2つの|」の並べ方が求める場合の数に一致します。 この場合の数は、まず8つの場所（「6つの○」と「2つの|」の合計）を用意しておき、仕切りの場所2つ（もしくは○の場所6つ）を選ぶ（選ばなかった場所には自動的にもう一方が入る）、として解け、答えは8C2=8C6=28{}_{8} C_{2} = {}_{8} C_6 = 28通りです。

一般化すると、nn種類から重複を許してkk個選ぶ組み合わせはn−1+kCk{}_{n-1+k} C_kです。

脱線したので元の問題に戻ると、11以上nn以下の整数をkk個選ぶ重複組み合わせはn−1+kCk{}_{n-1+k} C_kなので、これが答えです。

ところで、この二項係数を求めるのにもひと工夫必要です。

nCk=n!k!(n−k)!{}_n C_k = \frac{n!}{k!(n-k)!}

なので、

k!−1k!^{-1} と (n−k)!−1(n-k)!^{-1} が必要です。これを求めるにはフェルマーの小定理を使います。

pp を素数、aa を pp の倍数でない整数として ap−1≡1(mod p)a^{p-1} \equiv 1 (mod\, p) が成立する。（引用元）

よって、a×ap−2≡1(mod p)a \times a^{p-2}\equiv 1 (mod\, p) となるので、ap−2a^{p-2} は aa の逆元です。　 これは、繰り返し二乗法を用いてO(log⁡p)O(\log p)で求まります。

なお、この問題では必要ないですが、複数の二項係数を高速で求めたい場面は多々あります。そんな時は逆元テーブル（1!,2!,...,n!1!, 2!, ..., n!の逆元）を予め求めておく必要があります。それぞれ求めるとO(nlog⁡p)O(n \log p)かかりますが、最初に(n!)−1(n!)^{-1}をO(log⁡p)O(\log p)で求め、(n−1)!−1=(n!)−1×n(n-1)!^{-1} = (n!)^{-1} \times nであることを利用して後ろから計算していくとO(n+log⁡p)O(n + \log p)で求まります。

#参考

  1. AtCoder Beginner Contest 021 解説
  2. 「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜