結果

問題 No.2572 Midori on the grid
ユーザー yasunori
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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; // ab
return true;
}
return false;
}
template <typename T>
bool chmax(T &a, const T& b) {
if (a < b) {
a = b; // ab
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;
}
//
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0