QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#417195#6678. Gem Island 2RedreamMerTL 295ms487652kbC++171.9kb2024-05-22 16:01:352024-05-22 16:01:36

Judging History

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

  • [2024-05-22 16:01:36]
  • 评测
  • 测评结果:TL
  • 用时:295ms
  • 内存:487652kb
  • [2024-05-22 16:01:35]
  • 提交

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(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	init();
	cin >> a >> b >> c;
	rep(i, 1, a) for(int j = 0; j * i <= b; ++j) (f[i] += C(b - j * i + a - 1, a - 1));
	rep(i, 1, a) f[i] %= 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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 273ms
memory: 472516kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

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

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

score: 0
Accepted
time: 231ms
memory: 472460kb

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

score: 0
Accepted
time: 248ms
memory: 472640kb

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

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

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

score: 0
Accepted
time: 283ms
memory: 472596kb

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

score: 0
Accepted
time: 255ms
memory: 472648kb

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

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

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

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

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

score: 0
Accepted
time: 295ms
memory: 487508kb

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

score: 0
Accepted
time: 282ms
memory: 487652kb

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 278ms
memory: 483792kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: -100
Time Limit Exceeded

input:

14999999 15000000 14999999

output:


result: