田グリッド [yukicoder 1141]

https://yukicoder.me/problems/no/1141

前提知識

• 2次元累積和

解説

https://yukicoder.me/submissions/522972

上に前提知識がもし書いてあれば、そちらを先に学習しましょう（ここではちゃんと解説しないです）

ちょっと難しい。
ある矩形についての操作を行う問題なので、累積和とかが使えないか考えてみる。

二次元累積和っぽく、いらない所を消す感じで考えてみる

今回の問題は全体から塗りつぶされたマスの数を取り除いて、積を取るような問題になっている。
積の逆は割り算なので、割り算でうまいことできないか？

答え = 全体の積 ÷ 縦の積 ÷ 横の積 × (r,c)の数

となる。二次元累積和が分かっている人なら、何となく分かるだろう。
後は、mod10⁹+7は逆元があるので、全体の積、縦の積、横の積を前計算すれば、クエリに答えられる。

A[r][c] = 0

これがコーナーケースとしてある。
0が含まれていると、逆元がうまく計算できない。
これをうまく扱う方法があり、0を1にしてしまえば問題ない。

しかし、これでは答えが0になるケースをカバーできない。
縦横を黒く塗ると、白い領域が最大4箇所できる。
この部分に0が含まれていれば、答えは0になるので、二次元累積和を使って、
A[r][c]=1であれば1、そうでないなら0で二次元累積和を作っておき、
白い領域の総和を取って1以上（0が存在する）なら0を答えとする。

int H, W, Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;

    vector<vector<int>> A(H, vector<int>(W));
    rep(y, 0, H) rep(x, 0, W) cin >> A[y][x];

    Ruisekiwa2D r2d(W, H);
    rep(y, 0, H) rep(x, 0, W) if (A[y][x] == 0) {
        r2d.add(x, y, 1);
        A[y][x] = 1;
    }
    r2d.build();

    vector<mint> columns(W, 1);
    rep(x, 0, W) rep(y, 0, H) columns[x] *= A[y][x];
    vector<mint> rows(H, 1);
    rep(x, 0, W) rep(y, 0, H) rows[y] *= A[y][x];

    mint tot = 1;
    rep(y, 0, H) rep(x, 0, W) tot *= A[y][x];

    cin >> Q;
    rep(_, 0, Q) {
        int y, x; cin >> y >> x;
        y--; x--;

        int zero = 0;
        zero += r2d.get(0, x - 1, 0, y - 1); // LU
        zero += r2d.get(0, x - 1, y + 1, H - 1); // LD
        zero += r2d.get(x + 1, W - 1, 0, y - 1); // RU
        zero += r2d.get(x + 1, W - 1, y + 1, H - 1); // RD

        if (0 < zero) printf("0\n");
        else {
            mint ans = tot / columns[x] / rows[y] * A[y][x];
            printf("%d\n", ans.get());
        }
    }
}