Task: | Kortit II |
Sender: | NoelMatero |
Submission time: | 2024-11-09 18:44:07 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 3 |
#2 | ACCEPTED | 5 |
#3 | ACCEPTED | 26 |
#4 | ACCEPTED | 28 |
#5 | ACCEPTED | 38 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5 | details |
#2 | ACCEPTED | 0.01 s | 2, 3, 4, 5 | details |
#3 | ACCEPTED | 0.00 s | 3, 4, 5 | details |
#4 | ACCEPTED | 0.00 s | 4, 5 | details |
#5 | ACCEPTED | 0.06 s | 5 | details |
#6 | ACCEPTED | 0.07 s | 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;vector<vector<ll>> binomial;void calc_eulerian(int max_n) {Eulerian.assign(max_n + 1, vector<int>(max_n + 1, 0));Eulerian[0][0] = 1;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] = ((ll)(i - j) * Eulerian[i - 1][j - 1] % MOD +(ll)(j + 1) * Eulerian[i - 1][j] % MOD) % MOD;}}}}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 calc_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;}}void calc_binomial(int max_n) {binomial.assign(max_n + 1, vector<ll>(max_n + 1, 0));for (int i = 0; i <= max_n; ++i) {binomial[i][0] = 1;for (int j = 1; j <= i; ++j) {binomial[i][j] = (binomial[i - 1][j - 1] + binomial[i - 1][j]) % MOD;}}}ll D_E(int m, int b) {ll total = 0;if (Eulerian[m][b] == 0) return total;ll sign = 1;for (int k = 0; k <= m; k++) {if (b > m - k || m - k < 0) continue;ll Cmk = binomial[m][k];ll Ak = Eulerian[m - k][b];total = (total + sign * (Cmk * Ak % MOD)) % MOD;sign = MOD - sign;}return total;}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));}calc_factorials(max_n);calc_eulerian(max_n);calc_binomial(max_n);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 = binomial[n][c];ll f = (n - c >= 0 && b <= (n - c)) ? D_E(n - c, b) : 0LL;ll total = factorial[n] * C_nc % MOD;total = total * f % MOD;cout << total << "\n";}return 0;}
Test details
Test 1
Group: 1, 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
54 4 4 0 3 1 3 3 2 2 4 0 4 ... |
correct output |
---|
0 0 0 0 0 ... |
user output |
---|
0 0 0 0 0 ... |
Test 2
Group: 2, 3, 4, 5
Verdict: ACCEPTED
input |
---|
284 6 1 0 5 0 2 7 1 5 7 7 5 ... |
correct output |
---|
0 0 35280 0 36720 ... |
user output |
---|
0 0 35280 0 36720 ... |
Test 3
Group: 3, 4, 5
Verdict: ACCEPTED
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: ACCEPTED
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: ACCEPTED
input |
---|
1000 892 638 599 966 429 655 1353 576 1140 1403 381 910 ... |
correct output |
---|
0 0 0 249098285 0 ... |
user output |
---|
0 0 0 249098285 0 ... |
Test 6
Group: 5
Verdict: ACCEPTED
input |
---|
1000 2000 1107 508 2000 1372 249 2000 588 65 2000 1739 78 ... |
correct output |
---|
750840601 678722180 744501884 159164549 868115056 ... |
user output |
---|
750840601 678722180 744501884 159164549 868115056 ... |