結果
問題 |
No.1141 田グリッド
|
ユーザー |
![]() |
提出日時 | 2020-07-31 21:34:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 1,756 bytes |
コンパイル時間 | 1,452 ms |
コンパイル使用メモリ | 175,160 KB |
実行使用メモリ | 20,736 KB |
最終ジャッジ日時 | 2024-07-06 16:48:05 |
合計ジャッジ時間 | 5,468 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007; int main(){ int H, W; cin >> H >> W; vector<vector<long long>> A(H + 2, vector<long long>(W + 2, 1)); for (int i = 1; i <= H; i++){ for (int j = 1; j <= W; j++){ cin >> A[i][j]; } } vector<vector<long long>> P1 = A, P2 = A, P3 = A, P4 = A; for (int i = 1; i <= H + 1; i++){ for (int j = 1; j <= W + 1; j++){ P1[i][j] *= P1[i][j - 1]; P1[i][j] %= MOD; } } for (int j = 1; j <= W + 1; j++){ for (int i = 1; i <= H + 1; i++){ P1[i][j] *= P1[i - 1][j]; P1[i][j] %= MOD; } } for (int i = 1; i <= H + 1; i++){ for (int j = W; j >= 0; j--){ P2[i][j] *= P2[i][j + 1]; P2[i][j] %= MOD; } } for (int j = 0; j <= W; j++){ for (int i = 1; i <= H + 1; i++){ P2[i][j] *= P2[i - 1][j]; P2[i][j] %= MOD; } } for (int i = 1; i <= H + 1; i++){ for (int j = 1; j <= W + 1; j++){ P3[i][j] *= P3[i][j - 1]; P3[i][j] %= MOD; } } for (int j = 1; j <= W + 1; j++){ for (int i = H; i >= 0; i--){ P3[i][j] *= P3[i + 1][j]; P3[i][j] %= MOD; } } for (int i = 1; i <= H + 1; i++){ for (int j = W; j >= 0; j--){ P4[i][j] *= P4[i][j + 1]; P4[i][j] %= MOD; } } for (int j = 1; j <= W + 1; j++){ for (int i = H; i >= 0; i--){ P4[i][j] *= P4[i + 1][j]; P4[i][j] %= MOD; } } int Q; cin >> Q; for (int i = 0; i < Q; i++){ int r, c; cin >> r >> c; long long ans = 1; ans *= P1[r - 1][c - 1]; ans %= MOD; ans *= P2[r - 1][c + 1]; ans %= MOD; ans *= P3[r + 1][c - 1]; ans %= MOD; ans *= P4[r + 1][c + 1]; ans %= MOD; cout << ans << endl; } }