問題

解法

問題文の以下に注目

このプログラムの出力する答えは 1≦a1≦a2≦…≦ak≦n であるような整数の組 (a1,a2,…,ak) の個数に等しい

公式の解説に則ってこの文章を以下のように変換して考える。

「このプログラムの出力する答えは 1≦a1<a2<…<ak<n であるような整数の組 (a1,a2,…,ak) の個数に等しい」

こうするとa1~akはそれぞれ異なる数字となる。すると「組合せ問題」となりn個の中からk個選ぶ組合せ: nCk で求める事ができる。

また、元々の条件である「 1≦a1≦a2≦…≦ak≦n」を考察する。この条件はa1~akの値は同値の可能性が出て来る。よって、重複する数字を含むn個の数字の中からk個選ぶ組合せとなる。これを「重複組合せ」と呼び「nHk」と表す事ができる。

nHkは以下の公式で求める事ができる。

nHk = (n-1+k)C(n-1)

なぜ成り立つかは別の記事で示すことにする。(後日追記)

よって、結局、通常の組合せnCkを求める事ができればnHkを求める事ができる。

組合せは階乗と逆元を予め求める事でO(1)で取得することができる。MOD = 10⁹ + 7と置くと逆元はO(NlogMOD)で計算できる。

詳しくは以下の記事を参照

nCkがO(N log MOD)で取得できるのでnHkも同じ計算量で取得できる。