#935356 (C++17) No.2572 Midori on the grid

提出ソース

結果

問題	No.2572 Midori on the grid
ユーザー	あべし
提出日時	2023-12-02 16:55:40
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	184 ms / 5,000 ms
コード長	7,053 bytes
コンパイル時間	2,215 ms
コンパイル使用メモリ	206,776 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2023-12-02 16:55:47
合計ジャッジ時間	6,167 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	184 ms 6,676 KB
testcase_01	AC	89 ms 6,676 KB
testcase_02	AC	155 ms 6,676 KB
testcase_03	AC	129 ms 6,676 KB
testcase_04	AC	67 ms 6,676 KB
testcase_05	AC	139 ms 6,676 KB
testcase_06	AC	2 ms 6,676 KB
testcase_07	AC	2 ms 6,676 KB
testcase_08	AC	2 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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/output
template<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;
}

// setup
void set_fast_ios(size_t precision){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(precision);
    cerr << fixed << setprecision(precision);
}

// make_vector
template <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

// type
using 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>>;

// constant
constexpr 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};

// function
ll 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;}

// modint
template <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)-2
    vector<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;
        }
    }
}

yukicoder

結果

テストケース

ソースコード