結果
問題 | No.1141 田グリッド |
ユーザー |
![]() |
提出日時 | 2020-07-31 21:59:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,984 bytes |
コンパイル時間 | 1,610 ms |
コンパイル使用メモリ | 173,536 KB |
実行使用メモリ | 11,392 KB |
最終ジャッジ日時 | 2024-07-06 17:59:55 |
合計ジャッジ時間 | 5,611 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 WA * 10 |
ソースコード
//#define _GLIBCXX_DEBUG#include <bits/stdc++.h>#define FOR(i,a,b) for(ll i=a;i<b;i++)#define rep(i,n) FOR(i,0,n)#define ROF(i,a,b) for(ll i=a;i>=b;i--)#define per(i,a) ROF(i,a,0)#define pb push_backusing namespace std;using ll=long long;using ld=long double;using ch=char;typedef pair<ll,ll> P;typedef vector<ll> vl;typedef vector<vl> vvl;typedef vector<P> vP;typedef vector<ch> vc;typedef vector<vc> vvc;const ll MOD=1000000007;const ll MOD2=998244353;const ld PI=acos(-1);const ll INF=1e18;struct edge{ll to,cost;};struct edge2{ll from,to,cost;};template <typename T>bool chmax(T &a, const T& b) {if (a < b) {a = b;return true;}return false;}template <typename T>bool chmin(T &a, const T& b) {if (a > b) {a = b;return true;}return false;}ll pow_mod(ll x,ll y){if(y==0){return 1;}if(y%2==1){return x*pow_mod(x,y-1)%MOD;}else{ll t=pow_mod(x,y/2);return t*t%MOD;}}ll inv(ll x){return pow_mod(x,MOD-2);}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int H,W;cin >> H >> W;vvl A(H,vl(W,0));rep(i,H){rep(j,W){cin >> A[i][j];}}vvl acc0(H,vl(W,0));//yoko;vvl acc1(H,vl(W,0));ll sum=1;rep(i,H){rep(j,W){if(j==0){acc0[i][j]=A[i][j];}else{acc0[i][j]=(acc0[i][j-1]*A[i][j])%MOD;}}}rep(j,W){rep(i,H){if(i==0){acc1[i][j]=A[i][j];}else{acc1[i][j]=acc1[i-1][j]*A[i][j]%MOD;}}}rep(i,H){sum*=acc0[i][W-1];sum%=MOD;}ll Q;cin >> Q;rep(qq,Q){ll r,c;cin >> r >> c;r--;c--;cout << (sum*A[r][c])%MOD*(inv(acc0[r][W-1])*inv(acc1[H-1][c])%MOD)%MOD << endl;}}