QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#118065 | #6678. Gem Island 2 | UndertrainedOverpressure# | TL | 406ms | 355384kb | C++23 | 3.5kb | 2023-07-03 01:06:01 | 2023-07-03 01:06:02 |
Judging History
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