QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#600#118067#6678. Gem Island 2zhouhuanyiUndertrainedOverpressureSuccess!2024-04-23 17:43:252024-04-23 17:43:27

详细

Extra Test:

Time Limit Exceeded

input:

15000000 15000000 1

output:


result:


ID题目提交者结果用时内存语言文件大小提交时间测评时间
#118067#6678. Gem Island 2UndertrainedOverpressure#AC ✓1619ms355524kbC++236.6kb2023-07-03 01:19:052024-10-14 17:59:30

answer

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

#ifdef USE_MONT
template <uint32_t mod>
struct LazyMontgomeryModInt {
    using mint = LazyMontgomeryModInt;
    using i32 = int32_t;
    using u32 = uint32_t;
    using u64 = uint64_t;

    static constexpr u32 get_r() {
        u32 ret = mod;
        for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;
        return ret;
    }

    static constexpr u32 r = get_r();
    static constexpr u32 n2 = -u64(mod) % mod;
    static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
    static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
    static_assert(r * mod == 1, "this code has bugs.");

    u32 a;

    constexpr LazyMontgomeryModInt() : a(0) {}
    constexpr LazyMontgomeryModInt(const int64_t &b)
            : a(reduce(u64(b % mod + mod) * n2)){};

    static constexpr u32 reduce(const u64 &b) {
        return (b + u64(u32(b) * u32(-r)) * mod) >> 32;
    }

    constexpr mint &operator+=(const mint &b) {
        if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
        return *this;
    }

    constexpr mint &operator-=(const mint &b) {
        if (i32(a -= b.a) < 0) a += 2 * mod;
        return *this;
    }

    constexpr mint &operator*=(const mint &b) {
        a = reduce(u64(a) * b.a);
        return *this;
    }

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

    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 bool operator==(const mint &b) const {
        return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
    }
    constexpr bool operator!=(const mint &b) const {
        return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
    }
    constexpr mint operator-() const { return mint() - mint(*this); }
    constexpr mint operator+() const { return mint(*this); }

    constexpr mint pow(u64 n) const {
        mint ret(1), mul(*this);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    constexpr mint inverse() const {
        int x = get(), y = mod, u = 1, v = 0, t = 0, tmp = 0;
        while (y > 0) {
            t = x / y;
            x -= t * y, u -= t * v;
            tmp = x, x = y, y = tmp;
            tmp = u, u = v, v = tmp;
        }
        return mint{u};
    }

    friend ostream &operator<<(ostream &os, const mint &b) {
        return os << b.get();
    }

    friend istream &operator>>(istream &is, mint &b) {
        int64_t t;
        is >> t;
        b = LazyMontgomeryModInt<mod>(t);
        return (is);
    }

    constexpr u32 get() const {
        u32 ret = reduce(a);
        return ret >= mod ? ret - mod : ret;
    }

    static constexpr u32 get_mod() { return mod; }
};

using Mint = LazyMontgomeryModInt<998244353>;
#else
using uint = unsigned int;
using ull = unsigned long long;
template <uint MD> struct ModInt {
    using M = ModInt;
    // static int MD;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint((ull)v * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    bool operator!=(const M& r) const { return v != r.v; }
    M inv() const;
    friend istream& operator>>(istream& is, M& r) { ll x; is >> x; r = M(x); return is; }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};

template<uint MD>
ModInt<MD> pow(ModInt<MD> x, ll n) {
    ModInt<MD> r = 1;
    while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
    }
    return r;
}

template<uint MD>
ModInt<MD> ModInt<MD>::inv() const { return pow(*this, MD - 2); }
// or copy egcd and {return egcd(MD, v, 1).second;}

// if MD is from input
// this line is necessary, read later as you wish
// int ModInt::MD;

using Mint = ModInt<998244353>;
// using Mint = double;
#endif

const int M = 3e7 + 239;

Mint fact[M], inv[M];

Mint getC(int n, int k) {
    if (n < 0 || n < k || k < 0) {
        return 0;
    }
    return fact[n] * inv[n - k] * inv[k];
}

Mint precalc[M / 2];
Mint precalc2[M / 2];

void solve() {
    int n, d, r;
    n = 15000000;
    d = 15000000;
    r = 2;
    cin >> n >> d >> r;
    for (int i = r - 1; i < n; i++) {
        precalc[i] = getC(i, r - 1);
    }
    for (int idx = 0; idx < d; idx++) {
        precalc2[idx] = fact[n - 1 + idx] * inv[idx];
    }
    Mint ans = 0;
    for (int l = 1; l <= min(d, n); l++) {
        if (l > 1 && l <= r) {
            continue;
        }
        Mint sm = 0;
        int up = (d / l);
        for (int y = 1; y <= up; y++) {
            Mint cur = precalc2[d - l * y];
            if (l % 2 == 0) {
                cur = -cur;
            }
            if (l >= 2) {
                cur *= precalc[l - 2];
                if (r % 2 == 0) {
                    cur = -cur;
                }
            }
            sm += cur;
        }
        ans += sm * inv[n - l] * inv[l];
    }
    ans *= n;
    ans /= getC(n + d - 1, n - 1);
    ans += r;
    cout << ans << "\n";
}

int main() {
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    fact[0] = 1;
    for (int i = 1; i < M; i++) {
        fact[i] = fact[i - 1] * i;
    }
    inv[M - 1] = (Mint(1) / fact[M - 1]); //.inv();
    for (int i = M - 2; i >= 0; i--) {
        inv[i] = inv[i + 1] * (i + 1);
    }

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    cerr << TIME << "\n";

    return 0;
}