yukicoder No.1141 田グリッド

問題

H * Wのグリッドがあり、各マスには、非負整数A_ijが書かれている。
今、2個の整数(r,c)がQ個与えられるので、それぞれについて、その行rと列cを除いた部分の非負整数の積をmod 10^9+7で求めよ。

制約

• 2 <= H, W <= 10^5
• 4 <= H * W <= 10^5
• 0 <= A_ij <= 10^9
• 1 <= Q <= 5 * 10^4
• 1 <= r_i <= H
• 1 <= c_i <= W

解法

A_ijが0もあり得ることに注意。

0が1つでもある場合は、答えは0になるため、それ以外の答えになる場合というのは(r,c)ですべての0が除いている必要がある。

単純に、r行とc列の積をそれぞれ求めていて、後で割る、という求め方だと、0の配置の仕方のパターンがいくつか考えられ、実装がとても面倒になる。

効率的な方法は、求めるべき積の範囲が四隅からの長方形の形になっていることから、四隅からの累積値(累積和っぽく積を求める)をしておけば0のパターンを考えずに求められる。