Submission #70797675

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10, P = 998244353;

int n, d, a[N], f[N], fac[N], cnt[N], inv[N];

int fpm(int a, int b = P - 2, int p = P) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % p;
		b >>= 1, a = 1ll * a * a % p;
	}
	return res;
}

void init(int n = N - 1) {
	fac[0] = 1;
	for (int i = 1; i <= n; ++ i ) fac[i] = 1ll * fac[i - 1] * i % P;
	inv[n] = fpm(fac[n]);
	for (int i = n - 1; ~i; -- i ) inv[i] = 1ll * inv[i + 1] * (i + 1) % P;
}

int C(int n, int m) {
	return n >= m && m >= 0 ? 1ll * fac[n] * inv[m] % P * inv[n - m] % P : 0;
}

int work(int n, int m) {
	return n >= 0 && m >= 0 ? C(n + m - 1, m - 1) : 0;
}

int sum[N];

signed main() {
	init();
	
	cin >> n >> d;
	for (int i = 1; i <= n; ++ i ) {
		cin >> a[i];
		cnt[a[i]] ++ ;
	}
	sort(a + 1, a + n + 1);
	
	for (int i = 1; i <= 1e6; ++ i ) sum[i] = sum[i - 1] + cnt[i];
	
	int res = 1;
	for (int i = 1; i <= 1e6; ++ i )
		if (cnt[i]) {
			int p = sum[i - 1] - sum[max(0, i - d - 1)];
			res = 1ll * res * work(cnt[i], p + 1) % P;
		}
	cout << res;
	
	return 0;
}

Submission Info

Judge Result