ARC110D_FPS

https://gyazo.com/829c06c94c53cc49c05c234e5f3445c5

$ F_{i}(x) = \sum_{k=0}^{\infty} \binom{k}{A_{i}} x^{k}

$ G(x) = \prod_{i=1}^{N} F_{i}(x)

$ \binom{A+i}{A} = [x^i] \sum_n \binom{A+n}{A}x^n = [x^i]\frac{1}{(1-x)^{A+1}}

$ i < 0 の時 $ \binom{A+i}{A} = 0 であることから $ F_{i}(x) = \sum_{k=0}^{\infty} \binom{k}{A_{i}} 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}}

$ \displaystyle \sum_{i=0}^{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}} = \binom{A+B-1}{A-1}

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

参考

ほぼこれの流れ