かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC154 F - Many Many Paths

形式的冪級数を用いた解法です.

問題はこちら

問題概要

{2}次元グリッド上で{(0,0)}から{(r,c)}までの最短経路の個数を{f(r,c)}とする.{\displaystyle\sum_{r=r_1}^{r_2}\sum_{c=c_1}^{c_2}f(r,c)}を求めよ.

{1\leq r_1\leq r_2 \leq 10^6\\
1\leq c_1\leq c_2 \leq 10^6}

解説

{\displaystyle f(r,c)=\binom{r+c}{r}}である.これは高校数学なので,分からない場合は復習が必要.

{2}次元累積和の典型みたいに考えると{\displaystyle F(r,c)=\sum_{i=0}^{r}\sum_{j=0}^{c}f(i,j)}として{F(r_2,c_2)-F(r_1-1,c_2)-F(r_2,c_1-1)+F(r_1-1,c_1-1)}が答えなので{F(r,c)}を求める.

{\displaystyle F(r,c)=\sum_{i=0}^{r}\sum_{j=0}^{c}f(i,j)\\
=\displaystyle \sum_{i=0}^{r}\sum_{j=0}^{c}\binom{i+j}{i}}

{\displaystyle \sum_{j=0}^{c}\binom{i+j}{i}}{\displaystyle \sum_{j=0}^{\infty}\binom{i+j}{i}x^j}{0}から{c}次までの係数の和なので
{\displaystyle \sum_{j=0}^{c}\binom{i+j}{i}\\
=\displaystyle[x^c]\frac{\displaystyle\sum_{j=0}^{\infty}\binom{i+j}{i}x^j}{1-x}\\
=\displaystyle [x^c]\frac{1}{(1-x)^{i+2}}\\
=\displaystyle [x^c]\sum_{j=0}^{\infty}\binom{i+j+1}{i+1}x^j\\
=\displaystyle \binom{i+c+1}{i+1}}

よって,{\displaystyle F(r,c)=\sum_{i=0}^{r}\binom{i+c+1}{i+1}}
同様にして
{\displaystyle \sum_{i=0}^{r}\binom{i+c+1}{i+1}\\
=\displaystyle [x^r]\frac{\displaystyle\sum_{i=0}^{\infty}\binom{i+c+1}{i+1}x^i}{1-x}\\
=\displaystyle [x^{r+1}]\frac{\displaystyle\sum_{i=0}^{\infty}\binom{i+c+1}{i+1}x^{i+1}}{1-x}\\
=\displaystyle [x^{r+1}]\frac{1}{(1-x)^{c+2}}-\frac{1}{1-x}\\
=\displaystyle [x^{r+1}]\sum_{i=0}^{\infty}\binom{i+c+1}{i}x^i-\sum_{i=0}^{\infty}x^i\\
=\displaystyle\binom{r+c+2}{r+1}-1}

となり解ける.
{\displaystyle \sum_{j=0}^{c}\binom{i+j}{i}=[x^c]\frac{\displaystyle\sum_{j=0}^{\infty}\binom{i+j}{i}x^j}{1-x}}の変形が一番難しいのでここさえわかればいける.

{\displaystyle\frac{1}{(1-x)^{n+1}}=\sum_{i=0}^{\infty}\binom{n+i}{i}x^i}さえ知ってればすぐ思いつく.

提出プログラム

https://atcoder.jp/contests/abc154/submissions/22540407

感想

もっといい変形がありそう.