Many Many Paths [AtCoder Beginner Contest 154 F]

https://atcoder.jp/contests/abc154/tasks/abc154_f

前提知識

• 2次元累積和の考え方
• mod素数上での二項係数

解説

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

問われているのは、ある矩形区間での総和であるが、変数が4つもあるのは扱いにくい。
2次元累積和で使われている考え方を用いて、変数を2つに減らそう。
g(r,c) := 左下が(0,0)で、右上が(r,c)である矩形区間でのf(r,c)の総和
これを計算することができれば、g(r2, c2) - g(r1 - 1, c2) - g(r2, c1 - 1) + g(r1 - 1, c1 - 1)が答えとなる。
もし、これがあまりピンとこない場合は、2次元累積和について学ぶと良い。

これで変数が絞られたので、g(r,c)の計算方法を考えよう。
f(r,c)の計算方法を考えると、二項係数を使う方法が有名。
高校数学でもよく出てくる。これ
しかし、競技プログラミング的にはDPで解く方法も良く使われる。

DPにするとしたら、何を添字とするかとなるが、10⁶なので1変数しか使えない。
ここからひらめくと、以下のようなDPができる。
dp[rc] := r+c=rcである(r,c)についてf(r,c)の総和
もしDPで行くとしたら、これしか作れない感があるのだが、実はこれが計算可能。
これの遷移を見てみると、序盤はdp[rc+1] = dp[rc] * 2となっていることに気がつく。
途中では片方の端の要素だけ2倍とならず、最後は両端の要素だけ2倍とならない。
つまり、遷移をしていくが、2倍とならない要素だけ、引くことで計算ができる。
2倍とならない要素は両端の最大2個なので、そこだけ二項係数を使って計算して引いてやればいい。

最後は2倍とならない要素の判定方法である。
rcをインクリメントしていくのは、傾き-1の直線が平行移動していくようなイメージ。
その時に矩形区間と交わる部分が端となる。
端に注目すると、↑→と移動する点1と、→↑と移動する点2が、速度1で同時に移動しているような感じになる。
点1が→に移動する時は、遷移先に1回しか足されてないので、引く。
点2が↑に移動する時は、遷移先に1回しか足されてないので、引く。
よって、それぞれの点の座標を覚えておいて、遷移しながら移動させることで、引く要素を判定するといい感じ。

Comb<mint, 2010101> com;
//---------------------------------------------------------------------------------------------------
mint dp[2010101];
mint g(int R, int C) {
    dp[0] = 1;
    int r1 = 0, c1 = 0;
    int r2 = 0, c2 = 0;
    rep(rc, 0, R + C) {
        dp[rc + 1] = dp[rc] * 2;

        if (r1 != R) r1++;
        else {
            dp[rc + 1] -= com.aCb(r1 + c1, r1);
            c1++;
        }

        if (c2 != C) c2++;
        else {
            dp[rc + 1] -= com.aCb(r2 + c2, r2);
            r2++;
        }
    }
    mint res = 0;
    rep(rc, 0, R + C + 1) res += dp[rc];
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;

    mint ans = g(r2, c2) - g(r1 - 1, c2) - g(r2, c1 - 1) + g(r1 - 1, c1 - 1);
    cout << ans << endl;
}