Task: | Kortit II |
Sender: | Username* |
Submission time: | 2024-11-02 11:56:38 +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.06 s | 1, 2, 3, 4, 5 | details |
#2 | ACCEPTED | 0.06 s | 2, 3, 4, 5 | details |
#3 | ACCEPTED | 0.06 s | 3, 4, 5 | details |
#4 | ACCEPTED | 0.06 s | 4, 5 | details |
#5 | ACCEPTED | 0.07 s | 5 | details |
#6 | ACCEPTED | 0.07 s | 5 | details |
Code
#include <vector>#include <iostream>#include <cmath>#include <tuple>using namespace std;const int MOD = 1000000007;vector<vector<long long>> triangle() {vector<vector<long long>> tri(2001, vector<long long>(2001, 0));tri[1][1] = 0;tri[2][1] = 1;for (int n = 2; n < 2000; ++n) {for (int x = 1; x <= n; ++x) {tri[n + 1][x] = (x * tri[n][x] + (n + 1 - x) * tri[n][x - 1] + n * tri[n - 1][x - 1]) % MOD;}}return tri;}const vector<vector<long long>> tri = triangle();vector<vector<long long>> coeffs(int n) {vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));for (int i = 0; i <= n; i++) {C[i][0] = 1;C[i][i] = 1;}for (int i = 1; i <= n; i++) {for (int j = 1; j < i; j++) {C[i][j] = C[i - 1][j - 1] + C[i - 1][j] % MOD;}}return C;}const vector<vector<long long>> c = coeffs(2001);long long mpow(long long base, long long exp, long long mod) {long long result = 1;base = base % mod;while (exp > 0) {if (exp % 2 == 1) {result = (result * base) % mod;}exp = exp >> 1;base = (base * base) % mod;}return result;}long long fact(int n) {long long result = 1;for (int i = 1; i <= n; ++i) {result = (result * i) % MOD;}return result;}long long perm(int n, int x) {long long result = 1;for (int i = 0; i < x; ++i) {result = (result * (n - i)) % MOD;}return result;}long long solve(int n, int a, int b) {int req = (a + b);if (req > n || req == 1 || a == n || b == n) {return 0;}if (a == 0 && b == 0) {return fact(n);}int x = n - req;long long result = (tri[req][a] * fact(req) % MOD * fact(x) % MOD * mpow(c[n][x], 2, MOD)) % MOD;return result;}int main() {int t;cin >> t;vector<tuple<int, int, int>> inputs;for (int i = 0; i < t; ++i) {int n, a, b;cin >> n >> a >> b;inputs.push_back(make_tuple(n, a, b));}for (tuple<int, int, int> input : inputs) {int n, a, b;n = get<0>(input);a = get<1>(input);b = get<2>(input);int result = solve(n, a, b);cout << result << endl;}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 ... |