ARC110D
https://gyazo.com/829c06c94c53cc49c05c234e5f3445c5
考えたこと
N=2000だとO(N^2)なら大丈夫そう
M=10^9だと「最初のがxで残りがM-x」みたいな動的計画法は無理そう
BがAより小さくなると0になるので無視して良い
2000個の箱に残り$ R = M - \sum A_iを分配する
個別の事象は$ \binom{2000 + R}{R} ぐらいあるので個別に計算して足し合わせるのは間に合わない
→なんらかの式変形で束ねて計算できるはず
$ \sum_{i=0}^k \binom{n}{i}\binom{m}{k - i} = \binom{n+m}{k}
二項係数の積を一つの二項係数にしてて目的に近い
下の値を足したら一定というのも目的に近い
上の値が変わるので直接は使えない
これの亜種のような式があるはずだ→探そう
得たい$ f(A,B,K) = \sum_i \binom{A + i}{i}\binom{B + K - i}{K - i} を素朴に計算するコードを書いて観察
table::
1 1 1 4 4C1
1 1 2 10 5C2
1 1 3 20 6C3
→$ f(A,B,K) = \binom{A + B + K + 1}{K}
3項の場合
$ \sum_{ij} \binom{A_1 + i}{i} \binom{A_2 + j}{j} \binom{A_3 + (R - i - j))}{R - i - j}
$ = \sum_{i+j} \binom{A_1 + A_2 + (i+j) + 1 }{i+j} \binom{A_3 + (R - (i + j)))}{R - (i + j)}
$ = \sum_{k} \binom{A_1 + A_2 + k + 1 }{k} \binom{A_3 + (R - k))}{R - k}
$ = \binom{A_1 + A_2 + 1 + A_3 + R + 1}{R}
一般に
$ \sum A_i + (N - 1) (1 + R)
これは誤り see 追記A
この式でサンプル1を計算すると8になったが、途中の計算が雑なので怪しい
R以下の全パターンを出す必要があるはずなのにR=1の式で計算してるし
そもそもRは10^9ぐらいになりえるので二項係数の計算が無理っぽい？
これは誤り see 追記B
公式解説
$ S = \sum A_i として $ \binom{N+M}{S+N} が答え
R=M-Sなので$ \binom{N+M}{S+N} = \binom{N+M}{N+M-R} = \binom{N+M}{R}
なぜこうなるのか？
公式解説が自然言語で説明しているのは要するに下記の式
$ \sum_i \binom{i}{A}\binom{N-i-1}{B} = \binom{N}{A+B+1}
追記B
二項係数の計算
ついつい「高速に計算するために二項係数テーブルを作る」ってやりがち
ライブラリ作ったので…
なのだけど、今回のように二項係数の上が10^9、下が10^6の場合には$ C(n,m) = P(n,m) (m!)^{-1}でやるべきだった
この計算はO(m)にできるから
サイズnのテーブルを作るより速い
追記A
一般に
$ \sum A_i + (N - 1) (1 + R)
これは誤り
$ X= \sum A_i + (N - 1) + Rが正しい
$ R = M - \sum A_iなので $ X = M + N - 1
あれ、1合わないな…
この式は「振り分ける値」がちょうどRの場合だけを計算している
求める値は$ \sum_{r=0}^R \binom{S + N + r - 1}{r}
$ \sum_{i=0}^k \binom{n+i}{i} = \binom{n+k+1}{k}
これで1増えて、求める値は$ \binom{S + N + R }{R}
$ \binom{S + N + R }{R} = \binom{S + N + R }{S + N} = \binom{N + M}{S + N}
これで公式解説と同じ式に帰着した
→解説AC
今回は肉眼で判断してたけど終わってからOEIS使ったら楽チンだったので今度からそうする
「実験的に作った数列からの一般項の予想」をやらない道筋