#522187 (C++14) No.1141 田グリッド

• 問題: No.1141 田グリッド
• ユーザー: akun0716
• 提出日時: 2020-07-31 22:32:43
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 80 ms / 2,000 ms
• コード長: 2,162 bytes
• コンパイル時間: 886 ms
• コンパイル使用メモリ: 88,816 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-07-06 19:42:16
• 合計ジャッジ時間: 3,640 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 31

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
#define double long double
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
#define eps 1e-12 
//priority_queue<int,vector<int>, greater<int> > q2;
ll modpow(ll a, ll n = mod - 2) {
    ll r = 1;
    while (n) r = r * ((n % 2) ? a : 1) % mod, a = a * a%mod, n >>= 1;
    return r;
}
long long modinv(long long a) {
    return modpow(a, mod - 2);
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W; cin >> H >> W;
    vector<VI> A(H, VI(W));
    REP(i, H)REP(j, W)cin >> A[i][j];
    int sum = 1;
    VI a(H, 1), b(W, 1);
    VI zeroh(H, 0), zerow(W, 0);
    int zero = 0;
    REP(i, H) {
        REP(j, W) {
            if (A[i][j] == 0) {
                zero++;
                zeroh[i]++;
                zerow[j]++;
            }
            else {
                a[i] *= A[i][j];
                b[j] *= A[i][j];
                sum *= A[i][j];
                a[i] %= mod;
                b[j] %= mod;
                sum %= mod;
            }
        }
    }
    int ans;
    int Q; cin >> Q;
    while (Q--) {
        int R, C; cin >> R >> C;
        R--; C--;
        ans = sum;
        int tmp = zero - zeroh[R] - zerow[C];
        if (A[R][C] == 0)tmp++;
        if (tmp > 0) {
            cout << 0 << endl;
            continue;
        }
        ans *= modinv(a[R]);
        ans %= mod;
        ans *= modinv(b[C]);
        ans %= mod;
        if (A[R][C] != 0) {
            ans *= A[R][C];
            ans %= mod;
        }
        cout << ans << '\n';
    }
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX