[AtCoder] ABC154 F – Many Many Paths (600点)

2020年2月10日AtCoder二項係数, 600点, 二次元, 区間和

問題へのリンク

問題概要

2次元の平面上で、以下のように関数 f(r,c) を定義する。

f(r,c) := (0,0)から(r,c)までの経路の個数

この時、以下を計算せよ。ただし、\(10^9+7\) で割った余りで求めよ。

$$ \sum_{i=r_1}^{r_2}\sum_{j=c_1}^{c_2} f(i,j)$$

制約

  • \(1 \leq r_1 \leq r_2 \leq 10^6\)
  • \(1 \leq c_1 \leq c_2 \leq 10^6\)

考え方

問題は、以下のような平面上での区間和を求める問題とも言えます。

答えの範囲

ここで

$$F(r,c) :=\sum_{i=0}^{r}\sum_{j=0}^{c} f(i,j)$$

と定義します。これは問題よりも簡単な二次元区間和です。

F(r,c)の範囲

二次元区間和は、先程定義したような二次元区間和を4つ用いて計算することが多いです。つまり、

$$ F(r2,c2) – F(r1-1,c2) – F(r2, c1-1) + F(r1-1, c1 -1) $$

が答えになります。

4つの二次元区間和で表現する

解き方

先程定義した F(r,c) を高速に求めることができれば良いのが分かります。

以下の関係式を用いて式変形を行いましょう。

$$ f(i, j+1) = f(0, j) + f(1, j) + f(2, j) + \cdots + f(i, j) $$

横一列を一つにまとめる

これを利用することで以下のように計算することができます。

$$ F(r,c) = \sum_{j=1}^{c+1} f(r,j)$$

これは、f(i,j) の計算は二項係数を用いると O(1)で計算ができるので、F(r,c)の計算は O(c) で計算をすることができます。(もう一度同様の式変形を用いると O(1)で求めることもできます)

実装例