結果
問題 | No.1141 田グリッド |
ユーザー |
![]() |
提出日時 | 2020-07-31 21:55:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 3,611 bytes |
コンパイル時間 | 2,116 ms |
コンパイル使用メモリ | 203,908 KB |
最終ジャッジ日時 | 2025-01-12 09:55:25 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)#define rep(i, n) FOR(i, 0, n)#define ALL(x) begin(x), end(x)using namespace std;using ll = long long;constexpr ll Mod = 998244353;constexpr ll mod = 1e9 + 7;constexpr ll inf = 1LL << 60;const double PI = acos(-1);template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}/*-------------------------------------------*/template <int M> class ModInt {int x;public:constexpr ModInt() : x(0) {}constexpr ModInt(int64_t y) : x(y >= 0 ? y % M : (M - (-y) % M) % M) {}constexpr ModInt &operator+=(const ModInt p) {if((x += p.x) >= M) x -= M;return *this;}constexpr ModInt &operator-=(const ModInt p) {if((x += M - p.x) >= M) x -= M;return *this;}constexpr ModInt &operator*=(const ModInt p) {x = (int)(1LL * x * p.x % M);return *this;}constexpr ModInt &operator/=(const ModInt p) {*this *= p.inverse();return *this;}constexpr ModInt operator-() const { return ModInt(-x); }constexpr ModInt operator+(const ModInt p) const {return ModInt(*this) += p;}constexpr ModInt operator-(const ModInt p) const {return ModInt(*this) -= p;}constexpr ModInt operator*(const ModInt p) const {return ModInt(*this) *= p;}constexpr ModInt operator/(const ModInt p) const {return ModInt(*this) /= p;}constexpr bool operator==(const ModInt p) const { return x == p.x; }constexpr bool operator!=(const ModInt p) const { return x != p.x; }constexpr ModInt inverse() const {int a = x, b = M, u = 1, v = 0, t = 0;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return ModInt(u);}constexpr ModInt pow(int64_t k) const {ModInt ret(1), mul(x);while(k > 0) {if(k & 1) ret *= mul;mul *= mul;k >>= 1;}return ret;}constexpr friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;}constexpr friend istream &operator>>(istream &is, ModInt &a) {int64_t t = 0;is >> t;a = ModInt(t);return (is);}};using mint = ModInt<mod>;int h, w;int main() {cin.tie(nullptr);ios::sync_with_stdio(false);cin >> h >> w;vector<vector<mint>> v(h + 2, vector<mint>(w + 2, 1));FOR(i, 1, h + 1) FOR(j, 1, w + 1) cin >> v[i][j];vector<vector<mint>> v2, v3, v4;v2 = v3 = v4 = v;rep(i, h) rep(j, w) v[i + 1][j + 1] *= v[i + 1][j];rep(i, h) rep(j, w) v[i + 1][j + 1] *= v[i][j + 1];rep(i, h) FORR(j, w) v2[i + 1][j + 1] *= v2[i][j + 1];rep(i, h) FORR(j, w) v2[i + 1][j + 1] *= v2[i + 1][j + 2];FORR(i, h) rep(j, w) v3[i + 1][j + 1] *= v3[i + 2][j + 1];FORR(i, h) rep(j, w) v3[i + 1][j + 1] *= v3[i + 1][j];FORR(i, h) FORR(j, w) v4[i + 1][j + 1] *= v4[i + 2][j + 1];FORR(i, h) FORR(j, w) v4[i + 1][j + 1] *= v4[i + 1][j + 2];int q;cin >> q;rep(_, q) {int r, c;cin >> r >> c;mint ans(v[r - 1][c - 1]);ans *= v2[r - 1][c + 1];ans *= v3[r + 1][c - 1];ans *= v4[r + 1][c + 1];cout << ans << "\n";}return 0;}