QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#118063 | #6678. Gem Island 2 | UndertrainedOverpressure# | TL | 327ms | 238192kb | C++23 | 4.1kb | 2023-07-03 00:56:34 | 2023-07-03 00:56:37 |
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];
}
void solve() {
int n, d, r;
cin >> n >> d >> r;
Mint ans = getC(n + d - 1, n - 1) * r;
/*
for (int y = 1; y <= d; y++) {
for (int k = 1; k <= r; k++) {
for (int l = k; l * y <= d && l <= n; l++) {
Mint cur = getC(l - 1, k - 1) * getC(n, l) * getC(n + d - l * y - 1, d - l * y);
if ((l - k) % 2 == 1) {
cur = -cur;
}
ans += cur;
}
}
}
ans /= getC(n + d - 1, n - 1);
cout << ans << "\n";
return;
*/
for (int l = 1; l <= min(d, n); l++) {
for (int y = 1; l * y <= d; y++) {
Mint cur = getC(n - 1 + (d - l * y), d - l * y) * getC(n, l);
if (l % 2 == 0) {
cur = -cur;
}
/*Mint add = 0;
for (int k = 1; k <= min(r, l); k++) {
Mint sm = getC(l - 1, k - 1);
if ((k - 1) % 2 == 1) {
sm = -sm;
}
add += sm;
}
cur *= add;*/
if (l >= 2) {
int bd = min(r, l) - 1;
if (bd == l - 1) {
cur = 0;
} else {
cur *= getC(l - 2, bd);
if (bd % 2 == 1) {
cur = -cur;
}
}
}
ans += cur;
}
}
//cerr << ans << "\n";
ans /= getC(n + d - 1, n - 1);
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 289ms
memory: 238084kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 237ms
memory: 238084kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 274ms
memory: 238132kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 326ms
memory: 238068kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 266ms
memory: 238084kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 278ms
memory: 238192kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 310ms
memory: 238020kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 287ms
memory: 238100kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 327ms
memory: 238128kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 262ms
memory: 238092kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 282ms
memory: 238096kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 266ms
memory: 238080kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: -100
Time Limit Exceeded
input:
14999999 15000000 14999999