QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#447405#6678. Gem Island 2zhaohaikunAC ✓1125ms432248kbC++202.9kb2024-06-18 13:32:182024-06-18 13:32:19

Judging History

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

  • [2024-06-18 13:32:19]
  • 评测
  • 测评结果:AC
  • 用时:1125ms
  • 内存:432248kb
  • [2024-06-18 13:32:18]
  • 提交

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?
*/

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 469ms
memory: 355164kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

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

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

score: 0
Accepted
time: 481ms
memory: 355256kb

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

score: 0
Accepted
time: 473ms
memory: 355192kb

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

score: 0
Accepted
time: 501ms
memory: 355264kb

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

score: 0
Accepted
time: 491ms
memory: 355248kb

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

score: 0
Accepted
time: 442ms
memory: 355192kb

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

score: 0
Accepted
time: 439ms
memory: 355252kb

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

score: 0
Accepted
time: 490ms
memory: 355264kb

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

score: 0
Accepted
time: 483ms
memory: 355152kb

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

score: 0
Accepted
time: 462ms
memory: 355268kb

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 475ms
memory: 355216kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: 0
Accepted
time: 969ms
memory: 432160kb

input:

14999999 15000000 14999999

output:

29999999

result:

ok 1 number(s): "29999999"

Test #14:

score: 0
Accepted
time: 493ms
memory: 355612kb

input:

98765 99654 85647

output:

815183913

result:

ok 1 number(s): "815183913"

Test #15:

score: 0
Accepted
time: 455ms
memory: 355792kb

input:

99999 100000 99998

output:

832290200

result:

ok 1 number(s): "832290200"

Test #16:

score: 0
Accepted
time: 470ms
memory: 355712kb

input:

1541 99998 725

output:

463021366

result:

ok 1 number(s): "463021366"

Test #17:

score: 0
Accepted
time: 479ms
memory: 360372kb

input:

985438 998756 101254

output:

671487608

result:

ok 1 number(s): "671487608"

Test #18:

score: 0
Accepted
time: 495ms
memory: 360380kb

input:

998654 999856 2

output:

92085960

result:

ok 1 number(s): "92085960"

Test #19:

score: 0
Accepted
time: 477ms
memory: 360332kb

input:

45876 1000000 13

output:

208089291

result:

ok 1 number(s): "208089291"

Test #20:

score: 0
Accepted
time: 1083ms
memory: 432200kb

input:

15000000 14999999 514

output:

143843956

result:

ok 1 number(s): "143843956"

Test #21:

score: 0
Accepted
time: 1071ms
memory: 432100kb

input:

14985345 14999998 145124

output:

785676527

result:

ok 1 number(s): "785676527"

Test #22:

score: 0
Accepted
time: 1125ms
memory: 432248kb

input:

14855345 14993298 1451424

output:

779861797

result:

ok 1 number(s): "779861797"

Test #23:

score: 0
Accepted
time: 447ms
memory: 355264kb

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #24:

score: 0
Accepted
time: 918ms
memory: 432200kb

input:

15000000 15000000 15000000

output:

30000000

result:

ok 1 number(s): "30000000"

Extra Test:

score: 0
Extra Test Passed