結果
問題 | No.2572 Midori on the grid |
ユーザー |
![]() |
提出日時 | 2023-12-02 16:55:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 206 ms / 5,000 ms |
コード長 | 7,053 bytes |
コンパイル時間 | 2,135 ms |
コンパイル使用メモリ | 198,952 KB |
最終ジャッジ日時 | 2025-02-18 05:46:01 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 8 |
ソースコード
#include<bits/stdc++.h>using namespace std;// macro#define rep(i, N) for(ll i = 0; i < (ll)(N); ++i)#define per(i, N) for(ll i = (ll)(N) - 1; i >= 0; --i)#define all(v) (v).begin(), (v).end()#define rall(v) (v).rbegin(), (v).rend()#define bit(n, k) (((n) >> (k)) & 1)#define pcnt(n) (bitset<64>(n).count())#define endl '\n'#define fi first#define se second#define mkpr make_pair#define mktpl make_tuple#define eb emplace_back// input/outputtemplate<class T> istream& operator>>(istream& is, vector<T>& V){for(auto& it : V) is >> it;return is;}template<class T> ostream& operator<<(ostream& os, vector<T>& V){for(int i = 0; i < (int)V.size(); i++){os << V[i];os << (i + 1 != (int)V.size() ? " " : "");}return os;}template<class T1, class T2> istream& operator>>(istream& is, pair<T1, T2>& P){is >> P.first >> P.second;return is;}template<class T1, class T2> ostream& operator<<(ostream& os, pair<T1, T2> P){os << P.first << " " << P.second << "";return os;}// setupvoid set_fast_ios(size_t precision){cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(precision);cerr << fixed << setprecision(precision);}// make_vectortemplate <class T>vector<T> make_vector(size_t a, T b) {return vector<T>(a, b);}template <class... Ts>auto make_vector(size_t a, Ts... ts) {return vector<decltype(make_vector(ts...))>(a, make_vector(ts...));}// debug#ifdef LOCAL#define debug(x) cerr << "line"<< __LINE__ << ": " << #x << " = " << x << '\n'#define debugln() cerr << "line" << __LINE__ << ": passed.\n"#else#define debug(x, ...) void(0)#define debugln() void(0)#endif// typeusing ll = long long;using ull = unsigned long long;using ld = double;using i128 = __int128_t;using State = string::iterator;using Pair = pair<ll, ll>;using Tuple = tuple<ll, ll, ll>;template<class T> using max_heap = priority_queue<T>;template<class T> using min_heap = priority_queue<T, vector<T>, greater<T>>;template<class T> using vec = vector<T>;template<class T> using vvec = vec<vec<T>>;template<class T> using vvvec = vec<vvec<T>>;// constantconstexpr ll INF = 1001001001;constexpr ll LINF = 1001001001001001001ll;constexpr ll MOD998 = 998244353;constexpr ll MOD107 = (ll)(1e9+7);constexpr ll NIL = -1;constexpr ll pm[2] = {1, -1};constexpr ll dy[4] = {0, 1, 0, -1};constexpr ll dx[4] = {1, 0, -1, 0};constexpr ll dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};constexpr ll dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};// functionll Gcd(ll a, ll b){ return b ? Gcd(b, a % b) : abs(a);}ll Lcm(ll a, ll b){ return a / Gcd(a, b) * b;}template<class T> T powi(T x, ll exp){return exp > 0 ? (exp & 1 ? x : 1) * powi(x * x, exp >> 1) : x / x;}ll modpow(ll x, ll exp, ll mod){x %= mod;return exp > 0 ? (exp & 1 ? x : 1) * modpow(x * x, exp >> 1, mod) % mod : 1;}template<class T> bool chmin(T &a, T b){ return a > b ? (a = b, true) : 0;}template<class T> bool chmax(T &a, T b){ return a < b ? (a = b, true) : 0;}// modinttemplate <int mod> struct modint{long long x;modint() : x(0) {}modint(long long _x){ x = _x % mod; if(x < 0) x += mod; }constexpr modint operator-() const { return modint(-x); }constexpr modint& operator+=(const modint& a){ if ((x += a.x) >= mod) x -= mod; return *this; }constexpr modint& operator-=(const modint& a){ if ((x += mod - a.x) >= mod) x -= mod; return *this; }constexpr modint& operator*=(const modint& a){ (x *= a.x) %= mod; return *this; }constexpr modint& operator/=(const modint& a){ return (*this) *= a.mpow(mod-2); }constexpr modint operator+(const modint& a) const { return modint(*this) += a; }constexpr modint operator-(const modint& a) const { return modint(*this) -= a; }constexpr modint operator*(const modint& a) const { return modint(*this) *= a; }constexpr modint operator/(const modint& a) const { return modint(*this) /= a; }constexpr bool operator==(const modint& a) const { return (*this).x == a.x; }constexpr bool operator!=(const modint& a) const { return (*this).x != a.x; }constexpr const modint mpow(long long exp) const {modint res(1), x = *this;for(; exp; exp >>= 1){if(exp & 1) res *= x;x *= x;}return res;}friend istream& operator>>(istream& is, modint& m){ is >> m.x; m = modint<mod>(m.x); return is; }friend ostream& operator<<(ostream& os, const modint& m){ os << m.x; return os; }bool operator<(const modint& a) const { return (*this).x < a.x; }};constexpr ll MOD = MOD998;using mint = modint<MOD>;class Combination{int max_val; // (2^n)-2vector<long long> fact_, invf_;void build(int n){assert(n < MOD);int prev_val = max_val;while(max_val < n) max_val = (max_val << 1) | 2;max_val = min(max_val, n);fact_.resize(max_val + 1);invf_.resize(max_val + 1);for(int i = prev_val + 1; i <= max_val; i++){fact_[i] = fact_[i-1] * i % MOD;}invf_[max_val] = 1;for(long long x = fact_[max_val], k = MOD-2; k > 0; k >>= 1){if(k & 1) invf_[max_val] = invf_[max_val] * x % MOD;x = x * x % MOD;}for(int i = max_val; i > prev_val + 1; i--){invf_[i-1] = invf_[i] * i % MOD;}}bool check(int n){if(n < 0) return false;if(n > max_val) build(n);return true;}bool check(int n, int r){if(n < r || r < 0) return false;if(n > max_val) build(n);return true;}public:Combination() : max_val(0), fact_(1, 1), invf_(1, 1) {}Combination(int N) : max_val(0), fact_(1, 1), invf_(1, 1) {build(N);}long long fact(int n){if(!check(n)) return 0;return fact_[n];}long long invf(int n){if(!check(n)) return 0;return invf_[n];}long long nPr(int n, int r){if(!check(n, r)) return 0;return fact_[n] * invf_[n-r] % MOD;}long long nCr(int n, int r){if(!check(n, r)) return 0;return fact_[n] * invf_[n-r] % MOD * invf_[r] % MOD;}};int main(){set_fast_ios(15);int H, W, Q; cin >> H >> W >> Q;swap(H, W);Combination comb(H + W);auto L = [&](int t, int x) -> mint {if(t % 2 != abs(x) % 2) {return 0;} else {return comb.nCr(t, (t + x) / 2);}};auto low = [&](int t, int x, int l) -> mint {if(x < l) {return 0;} else {return L(t, x) - L(t, x - 2 * (l - 1));}};auto high = [&](int t, int x, int u) -> mint {return low(t, -x, -u);};while(Q--){int t; cin >> t;if(t > 0){cout << high(H + W, H - W, t - 1) << endl;}else{cout << low(H + W, H - W, t + 1) << endl;}}}