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

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)で求めることもできます)

実装例

#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
const int MOD = 1e9 + 7;
vector<long long> fact, fact_inv, inv;
/*  init_nCk :二項係数のための前処理
    計算量:O(n)
*/
void init_nCk(int SIZE) {
    fact.resize(SIZE + 5);
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        fact[i] = fact[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
}
/*  nCk :MODでの二項係数を求める(前処理 int_nCk が必要)
    計算量:O(1)
*/
long long nCk(int n, int k) {
    assert(!(n < k));
    assert(!(n < 0 || k < 0));
    return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD;
}
long long F(int r, int c) {
    long long ret = 0;
    FOR(j, 1, c + 2) {
        ret += nCk(r + j, j);
        ret %= MOD;
    }
    return ret;
}
int main() {
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    init_nCk(4000000);
    cout << (((F(r2, c2) + (MOD - F(r2, c1 - 1))) % MOD + (MOD - F(r1 - 1, c2))) % MOD + F(r1 - 1, c1 - 1)) % MOD
         << endl;
    return 0;
}