QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#907024 | #4228. Double Sort | zlt | WA | 10ms | 12392kb | C++14 | 1.7kb | 2025-02-20 12:35:33 | 2025-02-20 12:35:35 |
Judging History
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'