[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;
}
この記事が気に入ったらサポートをしてみませんか?