ARC110D nonFPS

ARC110Dの形式的べき級数を使わない解法

D - Binomial Coefficient is Fun

BiがAiより小さい時、二項係数は0になる
なのでBiが小さいケースは考える必要がない
$B_{i} = A_{i} + D_{i}$ とする。 $D_{i} \geq 0$
$S := \sum A_{i}$ として、残りを $R := M - S$ とする
$\sum D_{i} \leq R$ となる
「N個の枠にR個(以下)のボールを配る」の形になる
簡単のために2個の枠にちょうどK個のボールを配ることを考える
(0, K), (1, K-1), … , (K, 0) の配り方がある
求める解X2は $X_{2} = \sum_{i = 0}^{K} (A _{1} A _{1} + i) (A _{2} A _{2} + K - i)$ になる
これを素朴に実装していくつかの値について求め、そこから答えの式を予想する手もある(筆者はそうした)が、このページでは数式変形でやる
二項係数の対称性から $(A _{1} A _{1} + i) = (i A _{1} + i)$
$X_{2} = \sum_{i = 0}^{K} (i A _{1} + i) (K - i A _{2} + K - i)$ になる
重複組合せ: n個から重複を許してk個選ぶ方法の数
- $H_{k}^{n} = (k n + k - 1)$
重複組合せの形で書く:
- $X_{2} = \sum_{i = 0}^{K} H_{i}^{A_{1} + 1} H_{K - i}^{A_{2} + 1}$
シグマの中身はA1+1個からi個、A2+1個からK-i個選ぶ重複組合せ
可能な全てのiについて足し合わせたものは、A1+A2+2個からK個選ぶ重複組合せになる。
- $X_{2} = H_{K}^{A_{1} + A_{2} + 2}$
二項係数の形に戻す
- $X_{2} = (K A _{1} + A _{2} + K + 1)$
ここまででN=2でちょうどK個配る時の答えが一つの二項係数で表現できた
次は3以上のNについて考える
- 変数Kをiにリネームする
  - $X_{2} = (i A _{1} + A _{2} + i + 1)$
- この時、N=3の時のXはこうなる
  - $X_{3} = \sum_{i} (i A _{1} + A _{2} + i + 1) (K - i A _{3} + K - i)$
- これはA1がA1+A2+1になっただけなので上記の議論がそのまま使える
  - $X_{3} = (K A _{1} + A _{2} + 1 + A _{3} + K + 1) = (K A _{1} + A _{2} + A _{3} + K + 3 - 1)$
一般のNの時:
- $X_{N} = (K S + K + N - 1)$
- これはちょうどK個配る時の解だった
- 問題が求めている答えXはR以下のすべての和
  - $X = \sum_{K = 0}^{R} (K S + K + N - 1)$
ホッケースティック恒等式:
- $\sum_{i = 0}^{k} (i n + i) = (k n + k + 1)$
ホッケースティック恒等式で和を求める
- $X = \sum_{K = 0}^{R} (K S + K + N - 1) = \sum_{K = 0}^{R} (K S + N - 1 + K) = (R S + N - 1 + R + 1) = (R S + N + R)$
二項係数の対称性から
- $X = (R S + N + R) = (S + N S + N + R)$
$R := M - S$ なので
- $X = (S + N S + N + R) = (S + N N + M)$
これで求めるべき値が一つの二項係数にまとまった
N+Mは10^9ぐらいになるが、S+Nは10^7にならないので適切に実装すれば間に合う
- 巨大なnについての二項係数

🪴 Quartz 4.0

ARC110D nonFPS

Graph View

Backlinks