QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#118065#6678. Gem Island 2UndertrainedOverpressure#TL 406ms355384kbC++233.5kb2023-07-03 01:06:012023-07-03 01:06:02

Judging History

你现在查看的是最新测评结果

  • [2024-04-23 17:43:38]
  • hack成功,自动添加数据
  • (/hack/600)
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-03 01:06:02]
  • 评测
  • 测评结果:TL
  • 用时:406ms
  • 内存:355384kb
  • [2023-07-03 01:06:01]
  • 提交

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)

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;

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];

void solve() {
    int n, d, r;
    n = 15000000;
    d = 15000000;
    r = 10000000;
    cin >> n >> d >> r;
    for (int i = r - 1; i < n; i++) {
        precalc[i] = getC(i, r - 1);
    }
    Mint ans = 0;
    for (int l = 1; l <= min(d, n); l++) {
        Mint sm = 0;
        for (int y = 1; l * y <= d; y++) {
            int idx = d - l * y;
            Mint cur = fact[n - 1 + idx] * inv[idx];
            if (l % 2 == 0) {
                cur = -cur;
            }
            if (l >= 2) {
                int bd = min(r, l) - 1;
                if (bd == l - 1) {
                    cur = 0;
                } else {
                    cur *= precalc[l - 2];
                    if (bd % 2 == 1) {
                        cur = -cur;
                    }
                }
            }
            sm += cur;
        }
        ans += sm * getC(n, l);
    }
    ans *= inv[n - 1];
    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] = 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 335ms
memory: 355256kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

score: 0
Accepted
time: 327ms
memory: 355384kb

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

score: 0
Accepted
time: 326ms
memory: 355284kb

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

score: 0
Accepted
time: 298ms
memory: 355276kb

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

score: 0
Accepted
time: 341ms
memory: 355276kb

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

score: 0
Accepted
time: 326ms
memory: 355276kb

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

score: 0
Accepted
time: 289ms
memory: 355212kb

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

score: 0
Accepted
time: 366ms
memory: 355316kb

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

score: 0
Accepted
time: 341ms
memory: 355204kb

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

score: 0
Accepted
time: 321ms
memory: 355288kb

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

score: 0
Accepted
time: 368ms
memory: 355272kb

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 350ms
memory: 355276kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: 0
Accepted
time: 394ms
memory: 355384kb

input:

14999999 15000000 14999999

output:

29999999

result:

ok 1 number(s): "29999999"

Test #14:

score: 0
Accepted
time: 316ms
memory: 355284kb

input:

98765 99654 85647

output:

815183913

result:

ok 1 number(s): "815183913"

Test #15:

score: 0
Accepted
time: 356ms
memory: 355272kb

input:

99999 100000 99998

output:

832290200

result:

ok 1 number(s): "832290200"

Test #16:

score: 0
Accepted
time: 291ms
memory: 355284kb

input:

1541 99998 725

output:

463021366

result:

ok 1 number(s): "463021366"

Test #17:

score: 0
Accepted
time: 374ms
memory: 355320kb

input:

985438 998756 101254

output:

671487608

result:

ok 1 number(s): "671487608"

Test #18:

score: 0
Accepted
time: 401ms
memory: 355168kb

input:

998654 999856 2

output:

92085960

result:

ok 1 number(s): "92085960"

Test #19:

score: 0
Accepted
time: 406ms
memory: 355312kb

input:

45876 1000000 13

output:

208089291

result:

ok 1 number(s): "208089291"

Test #20:

score: -100
Time Limit Exceeded

input:

15000000 14999999 514

output:


result: