ARC110D

$F_{i} (x) = \sum_{k = 0}^{\infty} (A _{i} k) x^{k}$ $G (x) = \prod_{i = 1}^{N} F_{i} (x)$

下固定の二項係数→負の二項定理:
- $(A A + i) = [x^{i}] \sum_{n} (A A + n) x^{n} = [x^{i}] \frac{1}{( 1 - x ) ^{A + 1}}$
$i < 0$ の時 $(A A + i) = 0$ であることから $F_{i} (x) = \sum_{k = 0}^{\infty} (A _{i} k) x^{k} = \frac{x ^{A_{i}}}{( 1 - x ) ^{A_{i} + 1}}$

$S := \sum A_{i}$

$G (x) = \prod_{i = 1}^{N} F_{i} (x) = \frac{x ^{S}}{( 1 - x ) ^{S + N}}$

形式的べき級数の係数の部分和:
$i = 0 \sum k [x^{i}] F = [x^{k}] \frac{1}{1 - x} F$

$X = \sum_{i =}^{M} [x^{i}] G = [x^{M}] \frac{1}{1 - x} G = [x^{M}] \frac{x ^{S}}{( 1 - x ) ^{S + N + 1}}$ $= [x^{M - S}] \frac{1}{( 1 - x ) ^{S + N + 1}}$

べき級数→二項係数:
- $[x^{B}] \frac{1}{( 1 - x ) ^{A}} = (A - 1 A + B - 1)$

$[x^{M - S}] \frac{1}{( 1 - x ) ^{S + N + 1}} = (S + N S + N + 1 + M - S - 1) = (S + N N + M)$

参考

https://maspypy.com/atcoder-参加感想-2020-12-06arc110
- ほぼこれの流れ
https://twitter.com/kyopro_friends/status/1335227103797673984?s=21
https://twitter.com/maspy_stars/status/1335225085255319556?s=21
https://scol.hatenablog.com/entry/2020/12/06/015509

🪴 Quartz 4.0

ARC110D_FPS

Graph View

Backlinks