QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#118067 | #6678. Gem Island 2 | UndertrainedOverpressure# | AC ✓ | 1805ms | 355392kb | C++23 | 6.6kb | 2023-07-03 01:19:05 | 2023-07-03 01:19:07 |
Judging History
你现在查看的是测评时间为 2023-07-03 01:19:07 的历史记录
- [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:19:05]
- 提交
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;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 352ms
memory: 355268kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 343ms
memory: 355208kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 275ms
memory: 355276kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 316ms
memory: 355276kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 328ms
memory: 355320kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 255ms
memory: 355384kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 297ms
memory: 355212kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 323ms
memory: 355316kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 360ms
memory: 355320kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 331ms
memory: 355384kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 319ms
memory: 355292kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 343ms
memory: 355208kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 411ms
memory: 355380kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 362ms
memory: 355216kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 352ms
memory: 355268kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 340ms
memory: 355276kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 351ms
memory: 355208kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 315ms
memory: 355284kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 344ms
memory: 355280kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 1805ms
memory: 355312kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 683ms
memory: 355284kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 508ms
memory: 355292kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 332ms
memory: 355316kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 356ms
memory: 355392kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"