ARC110D nonFPS

https://gyazo.com/829c06c94c53cc49c05c234e5f3445c5

BiがAiより小さい時、二項係数は0になる

なのでBiが小さいケースは考える必要がない

「N個の枠にR個(以下)のボールを配る」の形になる

簡単のために2個の枠にちょうどK個のボールを配ることを考える

(0, K), (1, K-1), ... , (K, 0) の配り方がある

これを素朴に実装していくつかの値について求め、そこから答えの式を予想する手もある(筆者はそうした)が、このページでは数式変形でやる

$ H^n_k = \binom{n + k - 1}{k}

重複組合せの形で書く:

$ X_2 = \sum_{i=0}^K H^{A_1+1}_i H^{A_2+1}_{K-i}

シグマの中身はA1+1個からi個、A2+1個からK-i個選ぶ重複組合せ

可能な全てのiについて足し合わせたものは、A1+A2+2個からK個選ぶ重複組合せになる。

$ X_2 = H^{A_1+A_2+2}_K

二項係数の形に戻す

$ X_2 = \binom{A_1 + A_2 + K + 1}{K}

ここまででN=2でちょうどK個配る時の答えが一つの二項係数で表現できた

次は3以上のNについて考える

変数Kをiにリネームする

$ X_2 = \binom{A_1 + A_2 + i + 1}{i}

この時、N=3の時のXはこうなる

$ X_3 = \sum_i \binom{A_1 + A_2 + i + 1}{i} \binom{A_3 + K - i}{K - i}

これはA1がA1+A2+1になっただけなので上記の議論がそのまま使える

$ X_3 = \binom{A_1 + A_2 + 1 + A_3 + K + 1}{K} = \binom{A_1 + A_2 + A_3 + K + 3 - 1}{K}

一般のNの時:

$ X_N = \binom{S + K + N - 1}{K}

これはちょうどK個配る時の解だった

問題が求めている答えXはR以下のすべての和

$ X = \sum_{K=0}^R \binom{S + K + N - 1}{K}

$ \sum_{i=0}^k \binom{n+i}{i} = \binom{n+k+1}{k}

ホッケースティック恒等式で和を求める

$ X = \sum_{K=0}^R \binom{S + K + N - 1}{K} = \sum_{K=0}^R \binom{S + N - 1 + K}{K} = \binom{S + N - 1 + R + 1}{R} = \binom{S + N + R}{R}

二項係数の対称性から

$ X = \binom{S + N + R}{R} = \binom{S + N + R}{S + N}

$ X = \binom{S + N + R}{S + N} = \binom{N + M}{S + N}

これで求めるべき値が一つの二項係数にまとまった

N+Mは10^9ぐらいになるが、S+Nは10^7にならないので適切に実装すれば間に合う