QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#447406 | #2430. Gem Island | zhaohaikun | WA | 403ms | 355216kb | C++20 | 2.9kb | 2024-06-18 13:33:07 | 2024-06-18 13:33:08 |
Judging History
answer
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\033[32m[" << __LINE__ << "]\033[0m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x *= f;
}
const int N = 3e7 + 10, MOD = 998244353;
inline int power(int x, int y = MOD - 2) {
int ans = 1;
for (; y; x = (ll) x * x % MOD, y >>= 1)
if (y & 1) ans = (ll) ans * x % MOD;
return ans;
}
inline int& add(int &x, ll y) {return x = (x + y) % MOD;}
int n, d, r, t[N];
int fac[N], ifac[N], inv[N];
inline void binom(int x) {
fac[0] = ifac[0] = inv[1] = 1;
F(i, 2, x) inv[i] = (ll) (MOD - MOD / i) * inv[MOD % i] % MOD;
F(i, 1, x) fac[i] = (ll) fac[i - 1] * i % MOD, ifac[i] = (ll) ifac[i - 1] * inv[i] % MOD;
}
inline int C(int x, int y) {return x < y || y < 0 ? 0 : (ll) fac[x] * ifac[y] % MOD * ifac[x - y] % MOD;}
int p[N], ptot, ans;
bool vis[N];
void xxs(int n) {
F(i, 2, n) {
if (!vis[i]) p[++ptot] = i;
for (int j = 1; j <= ptot && p[j] * i <= n; j++) {
vis[i * p[j]] = true;
if (i % p[j] == 0) break;
}
}
}
int qq(int x, int y) {
if (!x) return 1;
int tt = C(x - 1, y);
if (y & 1) tt = MOD - tt;
return tt;
// int t = 1;
// F(i, 1, y) t = (ll) t * inv[i] % MOD * ((ll) y - x - i + 1 + MOD) % MOD;
// debug << x << " " << y << " " << tt << " " << t << endl;
// return t;
// int s = 0;
// F(i, 0, y) {
// int t = C(x, i);
// if (i & 1) add(s, MOD - t);
// else add(s, t);
// }
// return s;
}
int query(int x) {
int s = (ll) ((x & 1) ? x : MOD - x) * qq(x - 1, min(x, r) - 1) % MOD;
if (x > r) add(s, (ll) r * qq(x, x - r - 1));
// int ss = 0;
// F(i, r + 1, x) {
// int t = (ll) min(i, r) * C(x, i) % MOD;
// if ((x - i) & 1) add(ss, MOD - t);
// else add(ss, t);
// }
// debug << ss << " " << s << endl;
// debug << " -> " << x << " " << s << endl;
return s;
}
signed main() {
// freopen("count.in", "r", stdin);
// freopen("count.out", "w", stdout);
binom(3e7 + 5);
read(n), read(d), read(r);
F(i, 1, d) t[i] = C(d - i + n - 1, n - 1);
xxs(d);
F(i, 1, ptot)
DF(j, d / p[i], 1) add(t[j], t[j * p[i]]);
F(i, 1, min(n, d)) add(ans, (ll) C(n, i) * t[i] % MOD * query(i));//, debug << t[i] << " " << query(i) << endl;
int tot = C(d + n - 1, n - 1);
// debug << ans << ' ' << tot << endl;
cout << ((ll) ans * power(tot) + r) % MOD;
return 0;
}
/* why?
*/
Details
Test #1:
score: 0
Wrong Answer
time: 403ms
memory: 355216kb