結果

問題 No.1141 田グリッド
ユーザー southball02southball02
提出日時 2020-08-09 00:59:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,924 bytes
コンパイル時間 2,507 ms
コンパイル使用メモリ 212,596 KB
実行使用メモリ 9,088 KB
最終ジャッジ日時 2024-10-02 11:49:31
合計ジャッジ時間 5,224 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 3 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 3 ms
5,248 KB
testcase_12 AC 3 ms
5,248 KB
testcase_13 AC 64 ms
5,248 KB
testcase_14 AC 77 ms
9,088 KB
testcase_15 AC 62 ms
5,248 KB
testcase_16 AC 61 ms
5,248 KB
testcase_17 AC 61 ms
5,248 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 61 ms
5,248 KB
testcase_22 AC 60 ms
5,248 KB
testcase_23 AC 63 ms
5,248 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef _TEMPLATE_ROOT
#define _TEMPLATE_ROOT
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define repl(i, a, b) for(ll i = a; i < (b); ++i)
#define repd(i, a, b) for(int i = b; i >= (a); --i)
#define repdl(i, a, b) for(ll i = b; i >= (a); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
#endif
#ifndef _TEMPLATE_IO
#define _TEMPLATE_IO

template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void writef(T ...tail) { write(tail...); cout << flush; }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  if (v.size()) {
    rep(i, 0, sz(v) - 1)
      out << v[i] << " ";
    out << v.back();
  }
  return out;
}
#endif
#ifndef _TEMPLATE_MODINT
#define _TEMPLATE_MODINT

#ifndef _TEMPLATE_EUCLID
#define _TEMPLATE_EUCLID

ll euclid(ll a, ll b, ll &x, ll &y) {
	if (b) { ll d = euclid(b, a % b, y, x);
		return y -= a/b * x, d; }
	return x = 1, y = 0, a;
}
#endif
template<ll MOD = 1'000'000'007>
struct Mod {
	ll val;
	Mod() : val(0) {}
	Mod(ll xx) {
		if (0 <= xx && xx < MOD) val = xx;
		else val = (xx % MOD + MOD) % MOD;
	}
	Mod& operator+=(Mod b) { if ((val += b.val) >= MOD) val -= MOD; return *this; }
	Mod& operator-=(Mod b) { if ((val += MOD - b.val) >= MOD) val -= MOD; return *this; }
	Mod& operator*=(Mod b) { (val *= b.val) %= MOD; return *this; }
	Mod& operator/=(Mod b) { (val *= b.inv().val) %= MOD; return *this; }
	Mod operator+(Mod b) const { Mod<MOD> tmp(*this); return tmp += b; }
	Mod operator-(Mod b) const { Mod<MOD> tmp(*this); return tmp -= b; }
	Mod operator*(Mod b) const { Mod<MOD> tmp(*this); return tmp *= b; }
	Mod operator/(Mod b) const { Mod<MOD> tmp(*this); return tmp /= b; }
	Mod& operator++() { *this += 1; return *this; }
	Mod& operator--() { *this -= 1; return *this; }
	Mod operator++(int) { Mod<MOD> tmp(*this); operator++(); return tmp; }
	Mod operator--(int) { Mod<MOD> tmp(*this); operator--(); return tmp; }
	Mod inv() const {
		ll v, y, g = euclid(val, MOD, v, y);
		assert(g == 1); return Mod((v + MOD) % MOD);
	}
	Mod operator^(ll p) const {
		ll r = 1, b = val;
		for (; p; p >>= 1, b = b * b % MOD) if (p & 1) r = r * b % MOD;
		return Mod(r);
	}
	friend istream& operator>>(istream &is, Mod& mod) {
		ll tmp; is >> tmp;
		mod = Mod<MOD>(tmp);
		return is;
	}
	friend ostream& operator<<(ostream &os, const Mod& mod) {
		return os << mod.val;
	}
};
#endif
using namespace std;

typedef Mod<> modint;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

  int h, w; read(h, w);
  vector<vector<modint>> v(h, vector<modint>(w));
  vector<vector<int>> z(h, vector<int>(w));
  
  rep(i, 0, h)
    rep(j, 0, w) {
      read(v[i][j]);
      if (v[i][j].val == 0)
        z[i][j] = 1, v[i][j] = 1;
    }

  rep(i, 0, h)
    rep(j, 0, w) {
      z[i][j] +=
        (i ? z[i - 1][j] : 0)
        + (j ? z[i][j - 1] : 0)
        - (i && j ? z[i - 1][j - 1] : 0);
    }

  modint gs = 1;
  vector<modint> rs(h, 1), cs(w, 1);
  rep(i, 0, h)
    rep(j, 0, w)
      rs[i] *= v[i][j], cs[j] *= v[i][j], gs *= v[i][j];

  int q; read(q);
  rep(i, 0, q) {
    int r, c; read(r, c);
    --r; --c;
    if (z[h - 1][w - 1] - z[r][c] == 0)
      write(gs / rs[r] / cs[c] * v[r][c]);
    else
      write(0);
  }
}
0