CSES - Datatähti 2025 alku - Results
Submission details
Task:Kortit II
Sender:Touko_Ursin
Submission time:2024-11-01 09:57:32 +0200
Language:C++ (C++20)
Status:READY
Result:62
Feedback
groupverdictscore
#1ACCEPTED3
#2ACCEPTED5
#3ACCEPTED26
#4ACCEPTED28
#50
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5details
#2ACCEPTED0.00 s2, 3, 4, 5details
#3ACCEPTED0.01 s3, 4, 5details
#4ACCEPTED0.01 s4, 5details
#5--5details
#6--5details

Code

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
int fact(int val) {
long long res = 1;
while (val > 1) {
res = (res * val) % MOD;
val--;
}
return res;
}
long long comb(int tot, int sel) {
if (sel > tot) return 0;
if (sel == 0 || sel == tot) return 1;
vector<long long> dp(sel + 1, 0);
dp[0] = 1;
for (int x = 1; x <= tot; x++) {
for (int y = min(x, sel); y > 0; y--) {
dp[y] = (dp[y] + dp[y-1]) % MOD;
}
}
return dp[sel];
}
long long solve_rec(int down, int up, vector<vector<long long>>& dp) {
if (down < 0 || up < 0) return 0;
if (down == 0 && up == 0) return 1;
if (down + up <= 1) return 0;
if (dp[down][up] != -1) return dp[down][up];
long long ans = 0;
ans = (((long long)(down + up - 1) * solve_rec(down - 1, up - 1, dp)) % MOD);
ans = (ans + ((long long)down * solve_rec(down, up - 1, dp)) % MOD) % MOD;
ans = (ans + ((long long)up * solve_rec(down - 1, up, dp)) % MOD) % MOD;
return dp[down][up] = ans;
}
long long calc(int len, int same, int up, int down) {
if (same + up + down != len) return 0;
if (len <= 0 || same < 0 || up < 0 || down < 0) return 0;
vector<vector<long long>> dp(len + 1, vector<long long>(len + 1, -1));
long long p1 = comb(len, same);
long long p2 = solve_rec(down, up, dp);
return (p1 * p2) % MOD;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int q;
cin >> q;
while (q--) {
int n, up, down;
cin >> n >> up >> down;
int same = n - up - down;
long long ans = (calc(n, same, up, down) * fact(n)) % MOD;
cout << ans << "\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:

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:

input
1000
2000 1107 508
2000 1372 249
2000 588 65
2000 1739 78
...

correct output
750840601
678722180
744501884
159164549
868115056
...

user output
(empty)