https://atcoder.jp/contests/abc154/tasks/abc154_f
2次元グリッドにおいて、(0, 0)から($r, c$)まで移動する最短距離の数を$f(r, c)$と定義する。整数$r_1, c_1, r_2, c_2$が与えられるので、$r_1\leq i\leq r_2$かつ$c_1\leq j\leq c_2$を満たすすべての整数の組($i, j$)に対する$f(i, j)$の総和を求めよ。
$$\sum_{j=0}^{c} \binom{n+j}{j}=\binom{n+1}{c}$$ である。ここから $$\sum_{i=0}^{r} \sum_{j=0}^{c} \binom{i+j}{j}$$ がO($r$)で求められるので、これを使って二次元累積和のようにすれば解ける。
表を書いたのに気づかないのは駄目すぎるだろ。