AtCoder Beginner Contest 154-F - Many Many Paths
問題概要
縦 $x$ 本横 $y$ 本の道路が碁盤状にある街で，左下の地点から右上の地点までの最短経路の数を $f(x, y)$ とする．つまり， $$ f(x,y) = \binom{x+y}{x} = \binom{x+y}{y} = \frac{(x+y)\,!}{x\,!\;y\,!} $$とする．$0 \leq X_1 \leq X_2 \leq 10^6$, $0 \leq Y_1 \leq Y_2 \leq 10^6$ が与えられるので $$ \sum_{x=X_1}^{X_2} \sum_{y=Y_1}^{Y_2}f(x,y) $$ を (mod $10^9+7$ で) 計算せよ．
解説pdfの解法
$g(X,Y) = \sum_{x=0}^X\sum_{y=0}^Yf(x,y)$ とおけば，求める値は $$\begin{eqnarray} g(X_2, Y_2) - g(X_1 - 1, Y_2) - g(X_2, Y_1-1) + g(X_1 - 1, Y_1 - 1) \tag{1} \end{eqnarray}$$ と書ける．ところで
$$\begin{eqnarray} \sum_{x=0}^X f(x,Y) = f(X, Y+1) \tag{2} \end{eqnarray}$$ であるから， $$\begin{eqnarray} g(X,Y) = f(X+1, Y+1) - 1 \tag{3} \end{eqnarray}$$ が得られて，計算できる．
解答経緯
コンテスト中，式(1)には気がついて，$g$ を求める方法を考えていた．以下，$X\leq Y$とする．$0 \leq t \leq X+Y$ に対して $h(t) = \sum_{x+y = t}f(x,y)$ とおいて $g(X,Y) = \sum_{t=0}^{X+Y}h(t)$と書いた．$h(t)$は，最初のうちは倍々に増えていくが，そのうち，辺からこぼれるものが出てくるので， $$h(t)=\begin{cases} 1 & ( t = 0 )\\ 2 h(t-1) & ( t \leq X ) \\ 2 h(t-1) - f(t, X) & (X < t \leq Y) \\ 2 h(t-1) - f(t, X) - f(t, Y) & (Y < t) \end{cases}$$ という漸化式が書ける．これで提出して通った．
解けた解けた，と得意になっていたので，解説pdfをみてびっくり．(2)は意味を考えれば良い．(3)は(2)より従う．(3)も意味をつけられるが，ちと苦しいか．
まあ階乗があるので，どちらの解も $O(X+Y)$ ではあるけれども....
