[ABC154] F - Many Many Paths

[Q] https://atcoder.jp/contests/abc154/tasks/abc154_f

・考察
全地点の総和は出せない。2次元じゃなくて、行か列かをまとまて処理するような、1次元の処理ができないか探る。

  0  1  2  3  4  5 -> c
0 1  1  1  1  1  1
1 1  2  3  4  5  6
2 1  3  6 10 15 21
3 1  4 10 20 35 56
r

f(2,3) = 10について考える。
  0  1  2  3  4  5 -> c
0       1  
1       3  
2       6 10  // <= この10は、1 + 3 + 6 = f(0,2) + f(1,2) + f(2,2)であらわされる。
3         
r

一般化すると、
f(r, c) = f(0 ~ r, c - 1) の総和であらわされるようだ。
これを利用すればよさそう。

  0  1  2  3  4  5 -> c
0 1  1  1  1  1  1
1 1  2  3  4  5  6
2 1  3  6 10 15 21
3 1  4 10 20 35 56
r

(1,1) ~ (3,3)を求めたいとする。
  0  1  2  3  4  5 -> c
0  
1    2  3  4 
2    3  6 10 
3    4 10 20 
r

これを求めるには、
f(3,2) + f(3,3) + f(3,4)
から、
f(0,2) + f(0,3) + f(0,4)を引けばよさそうだ。

  0  1  2  3  4  5 -> c
0       1  1  1   
1 
2 
3      10 20 35 
r

(10 + 20 + 35) - (1 + 1 + 1)で求まった。

・実装

int main(){
  MOD = 1e9 + 7;
  cincout();
  COMinit();
  ll r[2], c[2];
  rep(i, 2) cin >> r[i] >> c[i];
  mint all = 0;
  // 列で足す
  for(ll i = c[0]; i <= c[1]; ++i){
    all += COM(r[1] + i + 1, i + 1);
  }
  mint dis = 0;
  for(ll i = c[0]; i <= c[1]; ++i){
    dis += COM(r[0] + i, i + 1);
  }
  // cerr << all << " " << dis << endl;
  cout << (all - dis) << endl;
}

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