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}$ を分配する
- 個別の事象は $(R 2000 + R)$ ぐらいあるので個別に計算して足し合わせるのは間に合わない
  - →なんらかの式変形で束ねて計算できるはず
- 二項係数の公式を眺める
- Vandermondeの恒等式
- $\sum_{i = 0}^{k} (i n) (k - i m) = (k n + m)$
  - 二項係数の積を一つの二項係数にしてて目的に近い
  - 下の値を足したら一定というのも目的に近い
  - 上の値が変わるので直接は使えない
  - これの亜種のような式があるはずだ→探そう
- 得たい $f (A, B, K) = \sum_{i} (i A + i) (K - i B + K - i)$ を素朴に計算するコードを書いて観察 : | 1 | 1 | 1 | 4 | 4C1 | | — | — | — | — | — | | 1 | 1 | 2 | 10 | 5C2 | | 1 | 1 | 3 | 20 | 6C3 |
  - → $f (A, B, K) = (K A + B + K + 1)$
- 3項の場合
  - $\sum_{ij} (i A _{1} + i) (j A _{2} + j) (R - i - j A _{3} + ( R - i - j )))$
  - $= \sum_{i + j} (i + j A _{1} + A _{2} + ( i + j ) + 1) (R - ( i + j ) A _{3} + ( R - ( i + j ))))$
  - $= \sum_{k} (k A _{1} + A _{2} + k + 1) (R - k A _{3} + ( R - k )))$
  - $= (R A _{1} + A _{2} + 1 + A _{3} + R + 1)$
- 一般に
- $\sum A_{i} + (N - 1) (1 + R)$
  - これは誤り see 追記A
- この式でサンプル1を計算すると8になったが、途中の計算が雑なので怪しい
  - R以下の全パターンを出す必要があるはずなのにR=1の式で計算してるし
- そもそもRは10^9ぐらいになりえるので二項係数の計算が無理っぽい？
  - これは誤り see 追記B
公式解説
- $S = \sum A_{i}$ として $(S + N N + M)$ が答え
- R=M-Sなので $(S + N N + M) = (N + M - R N + M) = (R N + M)$
- なぜこうなるのか？
  - 公式解説が自然言語で説明しているのは要するに下記の式
  - $\sum_{i} (A i) (B N - i - 1) = (A + B + 1 N)$
- 追記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} (r S + N + r - 1)$
    - ホッケースティック恒等式を使う
    - $\sum_{i = 0}^{k} (i n + i) = (k n + k + 1)$
  - これで1増えて、求める値は $(R S + N + R)$
  - $(R S + N + R) = (S + N S + N + R) = (S + N N + M)$
  - これで公式解説と同じ式に帰着した
→解説AC
形式的べき級数に帰着して解くこともできる
- ARC110D_FPS
OEIS
- https://twitter.com/yuruhiya/status/1335222719160315904?s=21
- 今回は肉眼で判断してたけど終わってからOEIS使ったら楽チンだったので今度からそうする
「実験的に作った数列からの一般項の予想」をやらない道筋
- 重複組合せの畳み込みだと解釈すれば素直に式変形できた
- 整理した: ARC110D_nonFPS

from ARC110

🪴 Quartz 4.0

ARC110D

Graph View

Backlinks