QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#666211#6678. Gem Island 2zltAC ✓651ms322248kbC++141.8kb2024-10-22 17:04:422024-10-22 17:04:48

Judging History

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

  • [2024-10-22 17:04:48]
  • 评测
  • 测评结果:AC
  • 用时:651ms
  • 内存:322248kb
  • [2024-10-22 17:04:42]
  • 提交

answer

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 30000100;
const ll mod = 998244353;

inline ll qpow(ll b, ll p) {
	ll res = 1;
	while (p) {
		if (p & 1) {
			res = res * b % mod;
		}
		b = b * b % mod;
		p >>= 1;
	}
	return res;
}

int n, m, K, N, fac[maxn], ifac[maxn], f[maxn], pr[maxn / 10], tot;
bool vis[maxn];

inline ll C(int n, int m) {
	if (n < m || n < 0 || m < 0) {
		return 0;
	} else {
		return 1LL * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
	}
}

void solve() {
	scanf("%d%d%d", &n, &m, &K);
	N = n + m;
	fac[0] = 1;
	for (int i = 1; i <= N; ++i) {
		fac[i] = 1LL * fac[i - 1] * i % mod;
	}
	ifac[N] = qpow(fac[N], mod - 2);
	for (int i = N - 1; ~i; --i) {
		ifac[i] = 1LL * ifac[i + 1] * (i + 1) % mod;
	}
	for (int i = 2; i <= m; ++i) {
		if (!vis[i]) {
			pr[++tot] = i;
		}
		for (int j = 1; j <= tot && i * pr[j] <= m; ++j) {
			vis[i * pr[j]] = 1;
			if (i % pr[j] == 0) {
				break;
			}
		}
	}
	for (int i = 1; i <= m; ++i) {
		f[i] = C(n + m - i - 1, n - 1);
	}
	for (int i = 1; i <= tot; ++i) {
		for (int j = m / pr[i], k = m / pr[i] * pr[i]; j; --j, k -= pr[i]) {
			int &t = f[j];
			t = (((t += f[k]) >= mod) ? t - mod : t);
		}
	}
	ll ans = 1LL * n * f[1] % mod;
	for (int i = 2; i <= n; ++i) {
		ans = (ans + C(n, i) * (((i - K) & 1) ? mod - 1 : 1) % mod * C(i - 2, K - 1) % mod * f[i]) % mod;
	}
	ans = ans * qpow(C(n + m - 1, n - 1), mod - 2) % mod;
	ans = (ans + K) % mod;
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 9972kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

score: 0
Accepted
time: 0ms
memory: 10052kb

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

score: 0
Accepted
time: 1ms
memory: 9916kb

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

score: 0
Accepted
time: 0ms
memory: 9988kb

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

score: 0
Accepted
time: 1ms
memory: 10036kb

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

score: 0
Accepted
time: 1ms
memory: 9980kb

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

score: 0
Accepted
time: 2ms
memory: 9960kb

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

score: 0
Accepted
time: 0ms
memory: 9992kb

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

score: 0
Accepted
time: 0ms
memory: 12040kb

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

score: 0
Accepted
time: 37ms
memory: 24388kb

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

score: 0
Accepted
time: 33ms
memory: 24304kb

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 28ms
memory: 22328kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: 0
Accepted
time: 566ms
memory: 320064kb

input:

14999999 15000000 14999999

output:

29999999

result:

ok 1 number(s): "29999999"

Test #14:

score: 0
Accepted
time: 5ms
memory: 12240kb

input:

98765 99654 85647

output:

815183913

result:

ok 1 number(s): "815183913"

Test #15:

score: 0
Accepted
time: 2ms
memory: 12236kb

input:

99999 100000 99998

output:

832290200

result:

ok 1 number(s): "832290200"

Test #16:

score: 0
Accepted
time: 3ms
memory: 10236kb

input:

1541 99998 725

output:

463021366

result:

ok 1 number(s): "463021366"

Test #17:

score: 0
Accepted
time: 29ms
memory: 31812kb

input:

985438 998756 101254

output:

671487608

result:

ok 1 number(s): "671487608"

Test #18:

score: 0
Accepted
time: 36ms
memory: 31248kb

input:

998654 999856 2

output:

92085960

result:

ok 1 number(s): "92085960"

Test #19:

score: 0
Accepted
time: 18ms
memory: 22608kb

input:

45876 1000000 13

output:

208089291

result:

ok 1 number(s): "208089291"

Test #20:

score: 0
Accepted
time: 639ms
memory: 318440kb

input:

15000000 14999999 514

output:

143843956

result:

ok 1 number(s): "143843956"

Test #21:

score: 0
Accepted
time: 651ms
memory: 322248kb

input:

14985345 14999998 145124

output:

785676527

result:

ok 1 number(s): "785676527"

Test #22:

score: 0
Accepted
time: 621ms
memory: 319048kb

input:

14855345 14993298 1451424

output:

779861797

result:

ok 1 number(s): "779861797"

Test #23:

score: 0
Accepted
time: 0ms
memory: 10052kb

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #24:

score: 0
Accepted
time: 574ms
memory: 320596kb

input:

15000000 15000000 15000000

output:

30000000

result:

ok 1 number(s): "30000000"

Extra Test:

score: 0
Extra Test Passed