QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#907024#4228. Double SortzltWA 10ms12392kbC++141.7kb2025-02-20 12:35:332025-02-20 12:35:35

Judging History

This is the latest submission verdict.

  • [2025-02-20 12:35:35]
  • Judged
  • Verdict: WA
  • Time: 10ms
  • Memory: 12392kb
  • [2025-02-20 12:35:33]
  • Submitted

answer

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1000100;
const int N = 1000000;
const int mod = 1000000007;

inline void fix(int &x) {
	x += ((x >> 31) & mod);
}

inline int qpow(int b, int p) {
	int res = 1;
	while (p) {
		if (p & 1) {
			res = 1LL * res * b % mod;
		}
		b = 1LL * b * b % mod;
		p >>= 1;
	}
	return res;
}

int n, m, fac[maxn], ifac[maxn], f[maxn], g[maxn];

inline int C(int n, int m) {
	if (n < m || n < 0 || m < 0) {
		return 0;
	} else {
		return 1LL * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
	}
}

void solve() {
	scanf("%d%d", &n, &m);
	fac[0] = 1;
	for (int i = 1; i <= N; ++i) {
		fac[i] = 1LL * fac[i - 1] * i % mod;
	}
	ifac[N] = qpow(fac[N], mod - 2);
	for (int i = N - 1; ~i; --i) {
		ifac[i] = 1LL * ifac[i + 1] * (i + 1) % mod;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; i * (j - 1) <= m; ++j) {
			fix(g[i] += C(m - i * (j - 1), n) - mod);
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= i; ++j) {
			int y = 1LL * ((j & 1) ? mod - 1 : 1) * C(i, j) % mod * C(n, i) % mod * g[n - i + j] % mod;
			fix(f[i + 1] += y - mod);
		}
	}
	for (int i = 1; i <= n; ++i) {
		fix(f[i] += f[i - 1] - mod);
	}
	for (int i = 1; i <= n; ++i) {
		fix(f[i] += f[i - 1] - mod);
	}
	for (int i = 1; i <= n; ++i) {
		printf("%lld\n", 1LL * f[i] * qpow(C(m, n), mod - 2) % mod);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 10ms
memory: 12392kb

input:

3 5

output:

1
100000003
500000008

result:

wrong answer 2nd numbers differ - expected: '2.3000000', found: '100000003.0000000', error = '43478261.1739130'