結果
問題 |
No.1141 田グリッド
|
ユーザー |
![]() |
提出日時 | 2020-08-01 04:32:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 234 ms / 2,000 ms |
コード長 | 3,292 bytes |
コンパイル時間 | 2,496 ms |
コンパイル使用メモリ | 210,044 KB |
最終ジャッジ日時 | 2025-01-12 12:09:59 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)n;++i) #define rrep(i,n) for(int i=(int)n-1;i>=0;--i) using namespace std; using ll = long long; template<typename T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;} template<typename T> inline bool chmin(T& a,T b){if(b<a){a=b;return 1;}return 0;} template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);} template<typename T,typename... Ts> auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));} template<typename T,typename U,typename... V> typename enable_if<is_same<T,U>::value>::type fill_v(U& u,const V... v){u=U(v...);} template<typename T,typename U,typename... V> typename enable_if<!is_same<T,U>::value>::type fill_v(U& u,const V... v){for(auto& e:u)fill_v<T>(e,v...);} const int mod = 1000000007; struct mint { long long x; mint(long long x=0) : x((x % mod + mod) % mod) {} mint operator-() const { return mint(-x);} mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint a) { if ((x += mod - a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;} mint operator+(const mint a) const { return mint(*this) += a;} mint operator-(const mint a) const { return mint(*this) -= a;} mint operator*(const mint a) const { return mint(*this) *= a;} mint pow(long long t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } mint inv() const { return pow(mod-2);} mint& operator/=(const mint a) { return *this *= a.inv();} mint operator/(const mint a) const { return mint(*this) /= a;} }; istream& operator>>(istream& is, mint& a) { return is >> a.x;} ostream& operator<<(ostream& os, const mint& a) { return os << a.x;} int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int h, w; cin >> h >> w; auto a = make_vec<int>(h, w); rep(i, h) rep(j, w) cin >> a[i][j]; auto sum = make_vec<mint>(4, h+1, w+1); fill_v<mint>(sum, 1); rep(i, h) rep(j, w) { if (sum[0][i][j].x == 0) sum[0][i+1][j+1] = 0; else sum[0][i+1][j+1] = sum[0][i][j+1] * sum[0][i+1][j] * a[i][j] / sum[0][i][j]; } rep(i, h) rrep(j, w) { if (sum[1][i][j+1].x == 0) sum[1][i+1][j] = 0; else sum[1][i+1][j] = sum[1][i][j] * sum[1][i+1][j+1] * a[i][j] / sum[1][i][j+1]; } rrep(i, h) rep(j, w) { if (sum[2][i+1][j].x == 0) sum[2][i][j+1] = 0; else sum[2][i][j+1] = sum[2][i][j] * sum[2][i+1][j+1] * a[i][j] / sum[2][i+1][j]; } rrep(i, h) rrep(j, w) { if (sum[3][i+1][j+1].x == 0) sum[3][i][j] = 0; else sum[3][i][j] = sum[3][i+1][j] * sum[3][i][j+1] * a[i][j] / sum[3][i+1][j+1]; } // rep(t, 4) { // rep(i, h+1) rep(j, w+1) { // cout << sum[t][i][j] << (j == w ? '\n' : ' '); // } // cout << endl; // } int q; cin >> q; while (q--) { int r, c; cin >> r >> c; r--; c--; mint ans = sum[0][r][c] * sum[1][r][c+1] * sum[2][r+1][c] * sum[3][r+1][c+1]; cout << ans << endl; } }