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}$を素朴に計算するコードを書いて観察 :

    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のテーブルを作るより速い
      • 巨大な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