QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#417200#6678. Gem Island 2RedreamMerAC ✓1976ms589844kbC++172.0kb2024-05-22 16:05:592024-05-22 16:06:01

Judging History

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

  • [2024-05-22 16:06:01]
  • 评测
  • 测评结果:AC
  • 用时:1976ms
  • 内存:589844kb
  • [2024-05-22 16:05:59]
  • 提交

answer

// #pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <vector>
#include <cstdio>
#include <random>
#include <iomanip>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;

#define PB emplace_back
#define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int) ((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
void print(vi n) { rep(i, 0, siz(n) - 1) cerr << n[i] << " \n"[i == siz(n) - 1]; }

const int N = 3e7, mod = 998244353;
int fac[N + 5], inv[N + 5];
int qp(int n, int m = mod - 2) {
	int res = 1;
	for (; m; m >>= 1) {
		if (m & 1) res = res * n % mod;
		n = n * n % mod;
	}
	return res;
}
void init() {
	fac[0] = fac[1] = 1;
	rep(i, 2, N) fac[i] = fac[i - 1] * i % mod;
	inv[N] = qp(fac[N]);
	per(i, N - 1, 0) inv[i] = inv[i + 1] * (i + 1) % mod;
}
int C(int n, int m) {return fac[n] * inv[m] % mod * inv[n - m] % mod;}
int a, b, c, f[N + 5];

signed main() {
	// freopen("count.in", "r", stdin);
	// freopen("count.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	init();
	cin >> a >> b >> c;
	rep(i, 1, b) f[i] = C(b - i + a - 1, a - 1);
	rep(i, 1, a) for(int j = 2; j * i <= b; ++j) (f[i] += f[i * j]);
	rep(i, 1, a) f[i] = (f[i] + C(b + a - 1, a - 1)) % mod;
	int ans = 0;
	auto sg = [&] (int x) {return x & 1 ? mod - 1 : 1;};
	if(c == 1) {
		rep(i, 1, c) rep(j, c, a) (ans += sg(j - i) * C(j - 1, i - 1) % mod * C(a, j) % mod * f[j]) %= mod;
	}
	else {
		(ans += a % mod * f[1]) %= mod;
		rep(j, c + 1, a) {
			(ans += sg(j - c) * C(j - 2, c - 1) % mod * C(a, j) % mod * f[j]) %= mod;
		}
	}
	cout << ans * qp(C(b + a - 1, a - 1)) % mod;
	return cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl, 0;
}

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

详细

Test #1:

score: 100
Accepted
time: 246ms
memory: 472656kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

score: 0
Accepted
time: 267ms
memory: 472508kb

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

score: 0
Accepted
time: 236ms
memory: 472580kb

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

score: 0
Accepted
time: 240ms
memory: 472612kb

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

score: 0
Accepted
time: 269ms
memory: 472616kb

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

score: 0
Accepted
time: 251ms
memory: 472676kb

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

score: 0
Accepted
time: 237ms
memory: 472600kb

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

score: 0
Accepted
time: 205ms
memory: 472620kb

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

score: 0
Accepted
time: 196ms
memory: 473504kb

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

score: 0
Accepted
time: 287ms
memory: 487460kb

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

score: 0
Accepted
time: 266ms
memory: 487700kb

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 264ms
memory: 483836kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: 0
Accepted
time: 1814ms
memory: 589768kb

input:

14999999 15000000 14999999

output:

29999999

result:

ok 1 number(s): "29999999"

Test #14:

score: 0
Accepted
time: 241ms
memory: 473324kb

input:

98765 99654 85647

output:

815183913

result:

ok 1 number(s): "815183913"

Test #15:

score: 0
Accepted
time: 223ms
memory: 473400kb

input:

99999 100000 99998

output:

832290200

result:

ok 1 number(s): "832290200"

Test #16:

score: 0
Accepted
time: 242ms
memory: 473380kb

input:

1541 99998 725

output:

463021366

result:

ok 1 number(s): "463021366"

Test #17:

score: 0
Accepted
time: 267ms
memory: 480420kb

input:

985438 998756 101254

output:

671487608

result:

ok 1 number(s): "671487608"

Test #18:

score: 0
Accepted
time: 285ms
memory: 480416kb

input:

998654 999856 2

output:

92085960

result:

ok 1 number(s): "92085960"

Test #19:

score: 0
Accepted
time: 241ms
memory: 480460kb

input:

45876 1000000 13

output:

208089291

result:

ok 1 number(s): "208089291"

Test #20:

score: 0
Accepted
time: 1976ms
memory: 589804kb

input:

15000000 14999999 514

output:

143843956

result:

ok 1 number(s): "143843956"

Test #21:

score: 0
Accepted
time: 1944ms
memory: 589844kb

input:

14985345 14999998 145124

output:

785676527

result:

ok 1 number(s): "785676527"

Test #22:

score: 0
Accepted
time: 1923ms
memory: 589736kb

input:

14855345 14993298 1451424

output:

779861797

result:

ok 1 number(s): "779861797"

Test #23:

score: 0
Accepted
time: 237ms
memory: 472612kb

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #24:

score: 0
Accepted
time: 1787ms
memory: 589836kb

input:

15000000 15000000 15000000

output:

30000000

result:

ok 1 number(s): "30000000"

Extra Test:

score: 0
Extra Test Passed