ABC021 D - 多重ループ - ツバサの備忘録

解法

答えの本質となる部分は問題文にすでに書いてあります。
求める数は、 $1 \leqq a_{1} \leqq a_{2} \leqq \cdots \leqq a_{k} \leqq n$ となるような $(a_{1},a_{2},\cdots ,a_{k})$ の組み合わせの個数です。
さて、 $1$ 以上 $n$ 以下の数字を $k$ 個重複を許しつつ抽出すると、それらの数字を利用して作成した $(a_{1},a_{2},\cdots ,a_{k})$ の組み合わせは一意に決まります。なぜなら、昇順になっていないといけないからです。
ということで、重複組み合わせの式 $_{n}H_{k}$ が求める答えになり、さらに式変形すると、結局求める値は
$_{n+k-1}C_{k}$ となります。
あとは、これを逆元なりなんなりを利用して求めれば、ACすることができます。
けんちょんさんのわかりやすい記事を例によって紹介しておきます。

qiita.com