結果
問題 |
No.1141 田グリッド
|
ユーザー |
![]() |
提出日時 | 2022-09-11 00:43:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 164 ms / 2,000 ms |
コード長 | 2,223 bytes |
コンパイル時間 | 1,903 ms |
コンパイル使用メモリ | 174,888 KB |
実行使用メモリ | 16,896 KB |
最終ジャッジ日時 | 2024-11-27 08:20:21 |
合計ジャッジ時間 | 7,605 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long mod = 1e9 + 7; int main() { int h, w; cin >> h >> w; vector<vector<long long>> a(h, vector<long long>(w)); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cin >> a[i][j]; } } vector<vector<long long>> b = a; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (j + 1 < w) { b[i][j + 1] *= b[i][j]; b[i][j + 1] %= mod; } } } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (i + 1 < h) { b[i + 1][j] *= b[i][j]; b[i + 1][j] %= mod; } } } vector<vector<long long>> c = a; for (int i = 0; i < h; i++) { for (int j = w - 1; j >= 0; j--) { if (j - 1 >= 0) { c[i][j - 1] *= c[i][j]; c[i][j - 1] %= mod; } } } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (i + 1 < h) { c[i + 1][j] *= c[i][j]; c[i + 1][j] %= mod; } } } vector<vector<long long>> d = a; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (j + 1 < w) { d[i][j + 1] *= d[i][j]; d[i][j + 1] %= mod; } } } for (int i = h - 1; i >= 0; i--) { for (int j = 0; j < w; j++) { if (i - 1 >= 0) { d[i - 1][j] *= d[i][j]; d[i - 1][j] %= mod; } } } vector<vector<long long>> e = a; for (int i = 0; i < h; i++) { for (int j = w - 1; j >= 0; j--) { if (j - 1 >= 0) { e[i][j - 1] *= e[i][j]; e[i][j - 1] %= mod; } } } for (int i = h - 1; i >= 0; i--) { for (int j = 0; j < w; j++) { if (i - 1 >= 0) { e[i - 1][j] *= e[i][j]; e[i - 1][j] %= mod; } } } int q; cin >> q; while (q--) { int x, y; cin >> x >> y; x--; y--; long long ans = 1; if (x - 1 >= 0 && y - 1 >= 0) ans *= b[x - 1][y - 1]; ans %= mod; if (x - 1 >= 0 && y + 1 < w) ans *= c[x - 1][y + 1]; ans %= mod; if (x + 1 < h && y - 1 >= 0) ans *= d[x + 1][y - 1]; ans %= mod; if (x + 1 < h && y + 1 < w) ans *= e[x + 1][y + 1]; ans %= mod; cout << ans << endl; } return 0; }