結果
問題 | No.2572 Midori on the grid |
ユーザー |
|
提出日時 | 2023-12-02 17:09:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,741 ms / 5,000 ms |
コード長 | 5,188 bytes |
コンパイル時間 | 2,102 ms |
コンパイル使用メモリ | 199,672 KB |
最終ジャッジ日時 | 2025-02-18 05:55:03 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 8 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T> using min_priority_queue = priority_queue<T,vector<T>,greater<T>>;template<typename T>void printv(vector<T> &v){bool b = false;for(auto i : v){if(b) cout << " ";else b = true;cout << i;}cout << endl;}template <typename T>bool chmin(T &a, const T& b) {if (a > b) {a = b; // aをbで更新return true;}return false;}template <typename T>bool chmax(T &a, const T& b) {if (a < b) {a = b; // aをbで更新return true;}return false;}template <typename T>T exEuclid(T a, T b, T &x, T &y){T d = a;if(b != 0){d = exEuclid(b, a%b, y, x);y -= (a/b)*x;}else{x = 1;y = 0;}//cout << a << " * " << x << " + " << b << " * " << y << " = " << d << endl;return d;}int64_t mod;struct modint{int64_t n;int64_t p;modint(){n = 0;p = mod;}modint(int64_t a){if(a <= -mod) a %= mod;else if(a >= mod) a %= mod;if(a < 0) a += mod;n = a;p = mod;}modint(int64_t a, int64_t q){if(a <= -q) a %= q;else if(a >= q) a %= q;if(a < 0) a += q;n = a;p = q;}modint pow(int64_t a){if(a <= 1-p) a %= p-1;else if(a >= p-1) a %= p-1;if(a < 0) a += p-1;modint rtn;if(n == 0) {rtn.n = 0;return rtn;}if(n == 1) {rtn.n = 1;return rtn;}if(a == 0) {rtn.n = 1;return rtn;}if(a == 1) {rtn.n = n;return rtn;}int64_t b = a/2;int64_t c = a%2;rtn = pow(b);rtn *= rtn;if(c){rtn *= modint(n);}return rtn;}modint operator+(modint other){modint rtn(n+other.n, p);return rtn;}modint operator-(modint other){modint rtn(n-other.n, p);return rtn;}modint operator*(modint other){modint rtn(n*other.n, p);return rtn;}modint operator/(modint other){int64_t x, y, d;d = exEuclid(other.n, p, x, y);int64_t rtn = x*n;if(d > 1) rtn /= d;return modint(rtn);}void operator+=(modint other){n += other.n;if(n >= p) n %= p;}void operator-=(modint other){n -= other.n;if(n < 0) n += p;}void operator*=(modint other){n *= other.n;if(n >= p) n %= p;}void operator/=(modint other){int64_t x, y, d;d = exEuclid(other.n, p, x, y);n *= x;if(d > 1) n /= d;if(n <= p || p <= n) n %= p;if(n < 0) n += p;return;}void operator++(){n++;if(n == p) n = 0;return;}void operator--(){n--;if(n == -1) n = p-1;return;}};vector<modint> fact_mod_v;vector<modint> inv_fact_mod_v;modint comb_mod(int64_t n, int64_t m){if(n < 0 || m < 0 || m > n) return 0;modint rtn = fact_mod_v[n]*inv_fact_mod_v[m]*inv_fact_mod_v[n-m];return rtn;}modint comb_mod_small(int64_t n, int64_t m){if(m < mod){return comb_mod(n%mod, m);}return comb_mod_small(n/mod, m/mod)*comb_mod(n%mod, m%mod);}void init_fact(int64_t n){fact_mod_v.resize(n+1,0);inv_fact_mod_v.resize(n+1,0);for(int64_t i = 0; i <= n; i++){if(i == 0){fact_mod_v[i] = modint(1);}else{fact_mod_v[i] = modint(i*fact_mod_v[i-1].n);}//cout << i << endl;}for(int64_t i = min(n, mod-1); i >= 0; i--){if(i == min(n, mod-1)){inv_fact_mod_v[i] = modint(fact_mod_v[i]).pow(-1);}else{inv_fact_mod_v[i] = modint(inv_fact_mod_v[i+1].n*(i+1));}//cout << i << endl;}}void yn(bool b){if(b) cout << "Yes" << endl;else cout << "No" << endl;}bool debug;bool randomInput;void input(){if(debug && randomInput){}else{}return;}void calc(){mod = 998244353;init_fact(200000);int H, W, Q;cin >> H >> W >> Q;for(int i = 0;i < Q; i++){int t; cin >> t;int h = H;int w = W;if(t < 0){t = -t;swap(h, w);}int d = h+t-w;if(d < 0){cout << 0 << endl;continue;}cout << (comb_mod(h+w,h)-comb_mod(h+w,h-d)).n << endl;}return;}int64_t ansSimple;void calcSimple(){return;}void calc1(){int t; cin >> t;for(int i = 0; i < t; i++){input();calc();calcSimple();}}int main(){debug = 0;randomInput = 0;srand(time(NULL));cout << fixed << setprecision(12);if(debug){calc1();}else{input();calc();}return 0;}//