結果
問題 |
No.1141 田グリッド
|
ユーザー |
![]() |
提出日時 | 2020-07-31 21:59:41 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 1,773 bytes |
コンパイル時間 | 1,274 ms |
コンパイル使用メモリ | 165,308 KB |
実行使用メモリ | 8,960 KB |
最終ジャッジ日時 | 2024-07-06 18:01:13 |
合計ジャッジ時間 | 3,209 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; #define fi first #define se second #define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep(i,n) repl(i,0,n) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<<x<<endl #define mmax(x,y) (x>y?x:y) #define mmin(x,y) (x<y?x:y) #define maxch(x,y) x=mmax(x,y) #define minch(x,y) x=mmin(x,y) #define uni(x) x.erase(unique(all(x)),x.end()) #define exist(x,y) (find(all(x),y)!=x.end()) #define bcnt __builtin_popcountll #define INF 1e16 #define mod 1000000007 ll mod_pow(ll x,ll n){ ll res=1; while(n>0){ if(n&1LL)res=res*x%mod; x=x*x%mod; n>>=1LL; } return res; } int main(){ cin.tie(0); ios::sync_with_stdio(false); int H,W; cin>>H>>W; vector<vector<ll>> A(H,vector<ll>(W)); rep(i,H)rep(j,W)cin>>A[i][j]; vector<ll> rsum(H,1),csum(W,1); ll tot=1; rep(i,H){ rep(j,W){ if(A[i][j]!=0)(rsum[i]*=A[i][j])%=mod; if(A[i][j]!=0)(csum[j]*=A[i][j])%=mod; if(A[i][j]!=0)(tot*=A[i][j])%=mod; } } vector<vector<ll>> cnt0(H+1,vector<ll>(W+1,0)); ll cnt0tot=0; rep(i,H)rep(j,W){ if(A[i][j]==0){ cnt0[i+1][j+1]=1; cnt0tot++; } } rep(i,H+1)rep(j,W)cnt0[i][j+1]+=cnt0[i][j]; rep(i,H)rep(j,W+1)cnt0[i+1][j]+=cnt0[i][j]; int Q; cin>>Q; while(Q--){ int r,c; cin>>r>>c; r--;c--; if((cnt0[r+1][W]-cnt0[r][W]-cnt0[r+1][0]+cnt0[r][0])+(cnt0[H][c+1]-cnt0[H][c]-cnt0[0][c+1]+cnt0[0][c])-(A[r][c]==0?1:0)<cnt0tot){ cout<<0<<"\n"; continue; } ll ans=tot; (ans*=mod_pow(rsum[r],mod-2))%=mod; (ans*=mod_pow(csum[c],mod-2))%=mod; if(A[r][c]!=0)(ans*=A[r][c])%=mod; cout<<ans<<"\n"; } return 0; }