提出 #41422173

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 998244353;

template <class T, class E>
constexpr T fexp(T x, E e) {
    T ans(1);
    for(; e > 0; e >>= 1) {
        if(e & 1) ans = ans * x;
        x = x * x;
    }
    return ans;
}

template <class LOW, class HIGH, const LOW mod>
struct modBase {
    using mint = modBase<LOW, HIGH, mod>;
    constexpr modBase() : val(0) {}
    // be careful of negative numbers!
    constexpr modBase(const LOW v) : val((v % mod + mod) % mod) {} 
    LOW val;

    #define add(a, b) a + b >= mod ? a + b - mod : a + b
    #define sub(a, b) a < b ? a + mod - b : a - b

    constexpr mint &operator += (const mint &o) { return val = add(val, o.val), *this; }
    constexpr mint &operator -= (const mint &o) { return val = sub(val, o.val), *this; }
    constexpr mint &operator *= (const mint &o) { return val = (LOW) ((HIGH) val * o.val % mod), *this; }
    constexpr mint &operator /= (const mint &o) { return *this *= o.inverse(); }

    constexpr mint operator + (const mint &b) const { return mint(*this) += b; }
    constexpr mint operator - (const mint &b) const { return mint(*this) -= b; }
    constexpr mint operator * (const mint &b) const { return mint(*this) *= b; }
    constexpr mint operator / (const mint &b) const { return mint(*this) /= b; }

    constexpr mint operator - () const { return mint() - mint(*this); }
    constexpr bool operator == (const mint &b) const { return val == b.val; }
    constexpr bool operator != (const mint &b) const { return val != b.val; }

    template<class E> constexpr mint pow (E e) const { return fexp(*this, e); }
    constexpr mint inverse() const { return pow(mod - 2); }
    constexpr LOW get() const { return val; }
    static constexpr LOW getMod() { return mod; }

    friend std::ostream& operator << (std::ostream &os, const mint &p) { return os << p.val; }
    friend std::istream& operator >> (std::istream &is, mint &p) { return is >> p.val; }
};

using mint = modBase<long long, long long, MOD>;

const int ms = 4020;

mint fat[ms], ifat[ms];
void initComb() {
    fat[0] = 1;
    for(int i = 1; i < ms; i++) {
        fat[i] = fat[i-1] * i;
    }
    ifat[ms-1] = fexp(fat[ms-1], MOD - 2);
    for(int i = ms-1; i > 0; i--) {
        ifat[i-1] = ifat[i] * i;
    }
}
mint comb(int n, int a) { return a < 0 || a > n ? mint() : fat[n] * ifat[a] * ifat[n-a]; }
mint bigComb(long long n, int a) {
    assert(n >= 0 && a >= 0 && a <= n);
    n %= MOD;
    //std::cout << "comb(" << n << ", " << a << ")\n";
    if(n < a) {
        //std::cout << "corner\n";
        return 0;
    }
    mint ans = ifat[a];
    //std::cout << "start with " << ans << '\n';
    for(int i = 0; i < a; i++) {
        assert((n - i + MOD) <= 2e9);
        mint cur((n - i + MOD) % MOD);
        assert(cur.val == n - i);
        ans *= cur;
        //std::cout << "multiplied by " << cur << " got " << ans << '\n';
    }
    return ans;
}

mint solve(int n, int k, long long ops) {
    if(ops < 0) {
        return 0;
    }
    // mint ans(0);
    // for(int i = 0; i <= ops; i++) {
    //     ans += comb(n-1+ops-i, n-1) * comb(n-k+i, n-k);
    // }
    // return ans;
    return bigComb(2 * n - k + ops, 2 * n - k);
}

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
    initComb();
    int k, n;
    long long ops;
    std::cin >> n >> ops >> k;
    if(ops % k != 0) {
        std::cout << "0\n";
        return 0;
    }
    ops /= k;
    mint ans(0);
    //std::cout << "there are " << ops << " ops\n";
    for(int i = 0; i <= n - k + 1; i++) {
        //std::cout << "for i " << i << " operating " << solve(n, k, ops - k * i) << " * " << comb(n - k + 1, i) << '\n';
        mint cur = solve(n, k, ops - k * i) * comb(n - k + 1, i);
        if(i % 2 == 0) {
            ans += cur;
        } else {
            ans -= cur;
        }
        //break;
    }
    std::cout << ans << '\n';
}

提出情報

ジャッジ結果