QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#198959#6678. Gem Island 2jeffqiAC ✓849ms597520kbC++202.0kb2023-10-03 19:38:412024-04-23 17:46:45

Judging History

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

  • [2024-04-23 17:46:45]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:849ms
  • 内存:597520kb
  • [2024-04-23 17:43:38]
  • hack成功,自动添加数据
  • (/hack/600)
  • [2023-10-03 19:38:42]
  • 评测
  • 测评结果:100
  • 用时:813ms
  • 内存:599232kb
  • [2023-10-03 19:38:41]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define ui unsigned int
#define ull unsigned ll
#define i128 __int128
using namespace std;

namespace qiqi {
	const int N = 3e7,P = 998244353;
	array<ll,N+1> fac,ifac; vi p;
	ll pow(ll b,ll k) {
		ll a = 1;
		for (; k; b = b*b%P,k >>= 1) {
			if (k&1) {
				a = a*b%P;
			}
		}
		return a;
	}
	void init(int n = N) {
		fac[0] = 1;
		for (int i = 1; i <= n; i++) {
			fac[i] = i*fac[i-1]%P;
		}
		ifac[n] = pow(fac[n],P-2);
		for (int i = n; i >= 1; i--) {
			ifac[i-1] = i*ifac[i]%P;
		}
		vi isp(n+1,1);
		for (int i = 2; i <= n; i++) {
			if (isp[i]) {
				p.eb(i);
			}
			for (auto x:p|views::take_while([&](int k) {return i*k <= n;})) {
				isp[i*x] = 0; if (!(i%x)) {break;}
			}
		}
	}
	ll C(int n,int m) {
		return m < 0 || n < m ? 0 : fac[n]*ifac[m]%P*ifac[n-m]%P;
	}
	void main() {
		init();
		int n,d,r;
		cin >> n >> d >> r;
		const int m = n-1+d;
		vi f(d+1); iota(f.begin(),f.end(),0);
		ranges::transform(f,f.begin(),[&](int x) {
			return C(m-x,n-1);
		});
		for (auto x:p) {
			for (int i = d/x; i >= 1; i--) {
				f[i] = (f[i]+f[i*x])%P;
			}
		}
		for (int i = 1; i <= d; i++) {
			f[i] = f[i]*C(n,i)%P;
		}
		int ans = 0;
		for (int i = 1; i <= min(n,d); i++) {
			ll k = f[i];
			if (i != 1) {
				k = k*C(i-2,r-1)%P;
				if ((i+r)%2) {
					k = -k;
				}
			}
			ans = (ans+k)%P;
		}
		ans = (ans*pow(C(m,n-1),P-2)+r)%P;
		cout << (ans+P)%P << '\n';
	}
}

int main() {
//	clock_t st = clock();
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
//	cin >> T;
	while (T--) {
		qiqi::main();
	}

//	cout << (double)(clock()-st)/CLOCKS_PER_SEC;
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 452ms
memory: 597512kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

score: 0
Accepted
time: 411ms
memory: 597316kb

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

score: 0
Accepted
time: 369ms
memory: 597316kb

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

score: 0
Accepted
time: 399ms
memory: 597424kb

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

score: 0
Accepted
time: 384ms
memory: 597444kb

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

score: 0
Accepted
time: 381ms
memory: 597472kb

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

score: 0
Accepted
time: 405ms
memory: 597520kb

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

score: 0
Accepted
time: 401ms
memory: 597248kb

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

score: 0
Accepted
time: 386ms
memory: 597244kb

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

score: 0
Accepted
time: 434ms
memory: 597460kb

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

score: 0
Accepted
time: 396ms
memory: 597424kb

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 383ms
memory: 597424kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: 0
Accepted
time: 780ms
memory: 597292kb

input:

14999999 15000000 14999999

output:

29999999

result:

ok 1 number(s): "29999999"

Test #14:

score: 0
Accepted
time: 374ms
memory: 597296kb

input:

98765 99654 85647

output:

815183913

result:

ok 1 number(s): "815183913"

Test #15:

score: 0
Accepted
time: 435ms
memory: 597512kb

input:

99999 100000 99998

output:

832290200

result:

ok 1 number(s): "832290200"

Test #16:

score: 0
Accepted
time: 384ms
memory: 597512kb

input:

1541 99998 725

output:

463021366

result:

ok 1 number(s): "463021366"

Test #17:

score: 0
Accepted
time: 408ms
memory: 597468kb

input:

985438 998756 101254

output:

671487608

result:

ok 1 number(s): "671487608"

Test #18:

score: 0
Accepted
time: 419ms
memory: 597320kb

input:

998654 999856 2

output:

92085960

result:

ok 1 number(s): "92085960"

Test #19:

score: 0
Accepted
time: 401ms
memory: 597392kb

input:

45876 1000000 13

output:

208089291

result:

ok 1 number(s): "208089291"

Test #20:

score: 0
Accepted
time: 823ms
memory: 597280kb

input:

15000000 14999999 514

output:

143843956

result:

ok 1 number(s): "143843956"

Test #21:

score: 0
Accepted
time: 829ms
memory: 597444kb

input:

14985345 14999998 145124

output:

785676527

result:

ok 1 number(s): "785676527"

Test #22:

score: 0
Accepted
time: 849ms
memory: 597424kb

input:

14855345 14993298 1451424

output:

779861797

result:

ok 1 number(s): "779861797"

Test #23:

score: 0
Accepted
time: 416ms
memory: 597400kb

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #24:

score: 0
Accepted
time: 781ms
memory: 597508kb

input:

15000000 15000000 15000000

output:

30000000

result:

ok 1 number(s): "30000000"

Extra Test:

score: 0
Extra Test Passed