QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#197038#6678. Gem Island 2jeffqiWA 445ms599316kbC++201.9kb2023-10-02 09:13:562023-10-02 09:13:57

Judging History

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

  • [2024-04-23 17:43:38]
  • hack成功,自动添加数据
  • (/hack/600)
  • [2023-10-02 09:13:57]
  • 评测
  • 测评结果:WA
  • 用时:445ms
  • 内存:599316kb
  • [2023-10-02 09:13:56]
  • 提交

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(m+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 = m/x; i >= 1; i--) {
				f[i] = (f[i]+f[i*x])%P;
			}
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			ll k = f[i]*C(n,i)%P;
			if (i > r) {
				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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 445ms
memory: 598036kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

score: -100
Wrong Answer
time: 379ms
memory: 599316kb

input:

3 3 2

output:

399297747

result:

wrong answer 1st numbers differ - expected: '698771052', found: '399297747'