結果
問題 | No.1141 田グリッド |
ユーザー |
![]() |
提出日時 | 2020-07-31 21:42:46 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 3,857 bytes |
コンパイル時間 | 1,996 ms |
コンパイル使用メモリ | 164,900 KB |
実行使用メモリ | 7,808 KB |
最終ジャッジ日時 | 2024-07-06 17:11:47 |
合計ジャッジ時間 | 4,491 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define int long long#define ii pair <int, int>#define app push_back#define all(a) a.begin(), a.end()#define bp __builtin_popcountll#define ll long long#define mp make_pair#define f first#define s second#define Time (double)clock()/CLOCKS_PER_SEC#define debug(x) std::cout << #x << ": " << x << '\n';const int N = 1e5+7, MOD = 1000 * 1000 * 1000 + 7;//need define int long longint mod(int n) {n %= MOD;if (n < 0) return n + MOD;else return n;}int fp(int a, int p) {int ans = 1, c = a;for (int i = 0; (1ll << i) <= p; ++i) {if ((p >> i) & 1) ans = mod(ans * c);c = mod(c * c);}return ans;}int dv(int a, int b) { return mod(a * fp(b, MOD - 2)); }struct M {ll x;M (int x_) {x = mod(x_);}M () {}M operator + (M y) {int ans = x + y.x;if (ans >= MOD)ans -= MOD;return M(ans);}M operator - (M y) {int ans = x - y.x;if (ans < 0)ans += MOD;return M(ans);}M operator * (M y) {return M(x * y.x % MOD);}M operator / (M y) {return M(x * fp(y.x, MOD - 2) % MOD);}M operator + (int y) {return (*this) + M(y);}M operator - (int y) {return (*this) - M(y);}M operator * (int y) {return (*this) * M(y);}M operator / (int y) {return (*this) / M(y);}M operator ^ (int p) {return M(fp(x, p));}void operator += (M y) {*this = *this + y;}void operator -= (M y) {*this = *this - y;}void operator *= (M y) {*this = *this * y;}void operator /= (M y) {*this = *this / y;}void operator += (int y) {*this = *this + y;}void operator -= (int y) {*this = *this - y;}void operator *= (int y) {*this = *this * y;}void operator /= (int y) {*this = *this / y;}void operator ^= (int p) {*this = *this ^ p;}};M f[N], inv[N];void prec() {f[0] = M(1);for (int i = 1; i < N; ++i)f[i] = f[i - 1] * M(i);inv[N - 1] = f[N - 1] ^ (MOD - 2);for (int i = N - 2; i >= 0; --i)inv[i] = inv[i + 1] * M(i + 1);}M C(int n, int k) {if (n < k)return M(0);elsereturn f[n] * inv[k] * inv[n - k];}vector <M> a[N];M row[N], col[N];int row0[N], col0[N], all0 = 0;signed main() {#ifdef HOMEfreopen("input.txt", "r", stdin);#else#define endl '\n'ios_base::sync_with_stdio(0); cin.tie(0);#endifint n, m;cin >> n >> m;for (int i = 0; i < n; ++i) {a[i].resize(m);for (int j = 0; j < m; ++j) {int x;cin >> x;a[i][j] = M(x);}}for (int i = 0; i < n; ++i) {row[i] = M(1);for (int j = 0; j < m; ++j) {if (a[i][j].x == 0)++row0[i];elserow[i] *= a[i][j];}}for (int j = 0; j < m; ++j) {col[j] = M(1);for (int i = 0; i < n; ++i) {if (a[i][j].x == 0)++col0[j];elsecol[j] *= a[i][j];}}M all = M(1);for (int i = 0; i < n; ++i)for (int j = 0; j < m; ++j) {if (a[i][j].x == 0)++all0;elseall *= a[i][j];}int q;cin >> q;while (q--) {int i, j;cin >> i >> j;--i; --j;int nul = all0 - row0[i] - col0[j] + (a[i][j].x == 0);if (nul > 0) {cout << 0 << endl;}else {if (a[i][j].x)cout << (all / (row[i] * col[j]) * a[i][j]).x << endl;elsecout << (all / (row[i] * col[j])).x << endl;}}}