ARC110D

NISHIO Hirokazu [Translate]
ARC110D
D - Binomial Coefficient is Fun
考えたこと
N=2000だとO(N^2)なら大丈夫そう
M=10^9だと「最初のがxで残りがM-x」みたいな動的計画法は無理そう
ホッケースティック恒等式を眺める→違いそう
BがAより小さくなると0になるので無視して良い
2000個の箱に残りR = M - \sum A_iを分配する
個別の事象は\binom{2000 + R}{R}ぐらいあるので個別に計算して足し合わせるのは間に合わない
→なんらかの式変形で束ねて計算できるはず
二項係数の公式を眺める
Vandermondeの恒等式
\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}を素朴に計算するコードを書いて観察
:11144C1
112105C2
113206C3
→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のテーブルを作るより速い
巨大な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

形式的べき級数に帰着して解くこともできる
ARC110D_FPS

OEIS
https://twitter.com/yuruhiya/status/1335222719160315904?s=21
今回は肉眼で判断してたけど終わってからOEIS使ったら楽チンだったので今度からそうする

「実験的に作った数列からの一般項の予想」をやらない道筋
重複組合せの畳み込みだと解釈すれば素直に式変形できた
整理した: ARC110D_nonFPS

from ARC110