ARC110D nonFPS
ARC110Dの形式的べき級数を使わない解法
BiがAiより小さい時、二項係数は0になる
なのでBiが小さいケースは考える必要がない
B_i = A_i + D_iとする。D_i \ge 0
S := \sum A_iとして、残りをR:= M - Sとする
\sum D_i \le Rとなる
「N個の枠にR個(以下)のボールを配る」の形になる
簡単のために2個の枠にちょうどK個のボールを配ることを考える
(0, K), (1, K-1), ... , (K, 0) の配り方がある
求める解X2はX_2 = \sum_{i=0}^K \binom{A_1 + i}{A_1}\binom{A_2 + K - i}{A_2}になる
これを素朴に実装していくつかの値について求め、そこから答えの式を予想する手もある(筆者はそうした)が、このページでは数式変形でやる
二項係数の対称性から\binom{A_1 + i}{A_1} = \binom{A_1 + i}{i}
X_2 = \sum_{i=0}^K \binom{A_1 + i}{i}\binom{A_2 + K - i}{K - i} になる
重複組合せ: n個から重複を許してk個選ぶ方法の数
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}
R:= M - Sなので
X = \binom{S + N + R}{S + N} = \binom{N + M}{S + N}
これで求めるべき値が一つの二項係数にまとまった
N+Mは10^9ぐらいになるが、S+Nは10^7にならないので適切に実装すれば間に合う
Related Pages
- →二項定理×ホッケースティック恒等式×vandermondeの恒等式×ARC110D×eq6-3をeq6-2に帰着×重複組合せの畳み込み×eq7-proof×二項係数の和とフィボナッチ×数え上げテクニック集→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]