ABC #154 F
\[S(r, c) = \sum_{i=0}^r \sum_{j=0}^c f(i, j)\]
とおくと, 求める値は
\[S(r_2, c_2) - S(r_1-1, c_2) - S(r_2, c_1-1) + S(r_1-1, c_1-1)\]となる. あとは \(S(r, c)\) をどう効率よく求めるかである.
ここで,
\[f(r + 1, c) = f(r, 0) + f(r, 1) + \cdots + f(r, c)\]である. \(f(r + 1, c)\) に到達するには道 \((r, i)\) 〜 \((r + 1, i)\) のどれかを通る. \(i\) 番目の道を通る組み合わせの数は \(f(r, i)\) にたどりつく組み合わせの数に等しいので, 上の式が成り立つことが分かる.
よって,
\[S(r, c) = f(1, c) + f(2, c) + \cdots + f(r+1, c)\]となる.
\[f(r, c + 1) = f(0, c) + f(1, c) + \cdots + f(r, c)\]が同様に成り立つので,
\[S(r, c) = f(r+1, c+1) - f(0, c) = f(r+1, c+1) - 1\]となる. なお, 当然ながら
\[f(r, c) = \combi{r+c}{c}\]である.