結果
問題 |
No.1141 田グリッド
|
ユーザー |
|
提出日時 | 2021-01-30 13:05:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 167 ms / 2,000 ms |
コード長 | 1,765 bytes |
コンパイル時間 | 2,072 ms |
コンパイル使用メモリ | 198,424 KB |
最終ジャッジ日時 | 2025-01-18 09:53:24 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
typedef long long ll; typedef long double ld; #include <bits/stdc++.h> using namespace std; const ll MOD = 1e9+7; template< typename T > T mod_pow(T x, T n, const T &p) { T ret = 1; while(n > 0) { if(n & 1) (ret *= x) %= p; (x *= x) %= p; n >>= 1; } return ret; } int main() { ll h,w; std::cin >> h>>w; vector<vector<ll>> a(h,vector<ll>(w,0)); vector<ll> rows(h,1), cols(w,1); ll zero_count = 0; vector<ll> zrows(h,0), zcols(w,0); ll sum = 1; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { std::cin >> a[i][j]; rows[i] *= a[i][j]; rows[i] %= MOD; cols[j] *= a[i][j]; cols[j] %= MOD; if(a[i][j]==0){ zero_count++; zrows[i]++; zcols[j]++; } } } vector<ll> ex(w,1),ex2(h,1); for (int i = 0; i < w; i++) { for (int j = 0; j < h; j++) { if( a[j][i]==0)continue; ex[i] *= a[j][i]; ex[i] %= MOD; } } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if( a[i][j]==0)continue; ex2[i] *= a[i][j]; ex2[i] %= MOD; } } for (int i = 0; i < h; i++) { sum *= ex2[i]; sum %= MOD; } ll q; std::cin >> q; for (int i = 0; i < q; i++) { ll r,c; std::cin >> r>>c; r--;c--; if(zrows[r]+zcols[c]-(a[r][c]==0) != zero_count ){ std::cout << 0 << std::endl; }else{ std::cout << sum * mod_pow(ex2[r], MOD-2, MOD) %MOD * mod_pow(ex[c], MOD-2, MOD) %MOD * (a[r][c]==0 ? 1 : a[r][c]) %MOD << std::endl; } } }