Task: | Kortit II |
Sender: | NoelMatero |
Submission time: | 2024-11-08 19:58:23 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
#4 | WRONG ANSWER | 0 |
#5 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.00 s | 1, 2, 3, 4, 5 | details |
#2 | WRONG ANSWER | 0.00 s | 2, 3, 4, 5 | details |
#3 | WRONG ANSWER | 0.00 s | 3, 4, 5 | details |
#4 | WRONG ANSWER | 0.01 s | 4, 5 | details |
#5 | TIME LIMIT EXCEEDED | -- | 5 | details |
#6 | TIME LIMIT EXCEEDED | -- | 5 | details |
Code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1000000007; vector<vector<int>> Eulerian; vector<ll> factorial, inv_factorial; void precompute_eulerian(int max_n) { Eulerian.assign(max_n + 1, vector<int>(max_n + 1, 0)); for (int i = 1; i <= max_n; i++) { for (int j = 0; j <= i - 1; j++) { if (j == 0) { Eulerian[i][j] = 1; } else { Eulerian[i][j] = ((long long)(i - j) * Eulerian[i - 1][j - 1] % MOD + (long long)(j + 1) * Eulerian[i - 1][j] % MOD) % MOD; } } } } int eulerian(int n, int m) { if (n < 0 || m < 0 || m >= n) return 0; return Eulerian[n][m]; } ll power_mod(ll a, ll b, ll mod_val) { ll res = 1; a %= mod_val; while (b > 0) { if (b & 1LL) { res = res * a % mod_val; } a = a * a % mod_val; b >>= 1LL; } return res; } void precompute_factorials(int n_max) { factorial.assign(n_max + 1, 1LL); inv_factorial.assign(n_max + 1, 1LL); for (int i = 1; i <= n_max; ++i) { factorial[i] = factorial[i - 1] * i % MOD; } inv_factorial[n_max] = power_mod(factorial[n_max], MOD - 2, MOD); for (int i = n_max - 1; i >= 0; i--) { inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD; } } ll comb(int n, int k) { if (k < 0 || k > n) return 0; return factorial[n] * inv_factorial[k] % MOD * inv_factorial[n - k] % MOD; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; vector<tuple<int, int, int>> tests(T); int max_n = 0; for (auto &x : tests) { cin >> get<0>(x) >> get<1>(x) >> get<2>(x); max_n = max(max_n, get<0>(x)); } precompute_factorials(max_n); precompute_eulerian(max_n); vector<vector<ll>> D_E(max_n + 1, vector<ll>(max_n + 1, 0LL)); for (int m = 0; m <= max_n; m++) { for (int b = 0; b <= m; b++) { ll total = 0; for (int k = 0; k <= m; k++) { ll Cmk = comb(m, k); if (b > m - k || m - k < 0) { continue; } ll Ak = Eulerian[m - k][b]; if (k & 1) { total = (total + MOD - (Cmk * Ak % MOD)) % MOD; } else { total = (total + (Cmk * Ak) % MOD) % MOD; } } D_E[m][b] = total; } } for (auto &x : tests) { int n, a, b; tie(n, a, b) = x; int c = n - a - b; if (c < 0 || c > n || a < 0 || b < 0) { cout << "0\n"; continue; } ll C_nc = comb(n, c); ll D = (n - c >= 0 && b <= (n - c)) ? D_E[n - c][b] : 0LL; ll total = factorial[n] * C_nc % MOD; total = total * D % MOD; cout << total << "\n"; } return 0; }
Test details
Test 1
Group: 1, 2, 3, 4, 5
Verdict: WRONG ANSWER
input |
---|
54 4 4 0 3 1 3 3 2 2 4 0 4 ... |
correct output |
---|
0 0 0 0 0 ... |
user output |
---|
999999983 0 0 0 0 ... |
Test 2
Group: 2, 3, 4, 5
Verdict: WRONG ANSWER
input |
---|
284 6 1 0 5 0 2 7 1 5 7 7 5 ... |
correct output |
---|
0 0 35280 0 36720 ... |
user output |
---|
4320 0 35280 0 36720 ... |
Test 3
Group: 3, 4, 5
Verdict: WRONG ANSWER
input |
---|
841 19 3 12 19 19 13 19 7 13 20 11 15 ... |
correct output |
---|
40291066 0 0 0 0 ... |
user output |
---|
40291066 0 0 0 0 ... |
Test 4
Group: 4, 5
Verdict: WRONG ANSWER
input |
---|
1000 15 12 6 7 1 6 44 4 26 6 6 5 ... |
correct output |
---|
0 5040 494558320 0 340694548 ... |
user output |
---|
0 5040 494558320 0 340694548 ... |
Test 5
Group: 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 892 638 599 966 429 655 1353 576 1140 1403 381 910 ... |
correct output |
---|
0 0 0 249098285 0 ... |
user output |
---|
(empty) |
Test 6
Group: 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 2000 1107 508 2000 1372 249 2000 588 65 2000 1739 78 ... |
correct output |
---|
750840601 678722180 744501884 159164549 868115056 ... |
user output |
---|
(empty) |