CSES - Datatähti 2025 alku - Results
Submission details
Task:Kortit II
Sender:OorigamiK
Submission time:2024-11-09 10:12:17 +0200
Language:C++ (C++20)
Status:READY
Result:8
Feedback
groupverdictscore
#1ACCEPTED3
#2ACCEPTED5
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1, 2, 3, 4, 5details
#2ACCEPTED0.05 s2, 3, 4, 5details
#30.06 s3, 4, 5details
#40.06 s4, 5details
#50.05 s5details
#60.06 s5details

Code

#include <iostream>
#include <vector>

long long sequance[2001][1001]; // n,r
long long factorials[2001];
long long choose[2001][2001];

const int MOD = 1000000007;

int min(int a, int b) {
	if (a < b) {
		return a;
	}
	return b;
}

int max(int a, int b) {
	if (a < b) {
		return b;
	}
	return a;
}

void calc_sequance() {
	sequance[0][1] = 0;
	for (int i = 1; i <= 1000; i++) {
		sequance[i][i] = 1;
		sequance[i-1][i] = 0;
	}
	for (int i = 1; i <= 2000; i++) {
		sequance[i][1] = 1;
		sequance[i][0] = 0;
	}
	for (int r = 2; r < 1000;r++) {
		for (int n = r; n < 2000; n++) {
			sequance[n+1][r] = (r * sequance[n][r] + (n + 2 - r) * sequance[n][r - 1] + (n+1) * sequance[n - 1][r - 1])%MOD;
		}
	}
}

void calc_factorials() {
	factorials[0] = 1;
	for (int i = 0; i < 2000; i++) {
		factorials[i + 1] = (factorials[i] * (i + 1))%MOD;
	}
}

void calc_nCk() {
	for (int n = 0; n <= 2000; n++) {
		choose[n][0] = 1;
		//choose[0][n] = 1;
	}
	for (int n = 0; n < 2000; n++) {
		for (int k = 0; k < 2000; k++) {
			choose[n + 1][k + 1] = (choose[n][k + 1] + choose[n][k]) % MOD;
		}
	}
}

int main()
{
	std::vector<int> nums;
	int t;
	std::cin >> t;
	for (int i = 0; i < t; i++) {
		int n,a,b;
		std::cin >> n >> a >> b;
		//std::cout << n << " " << a << " " << b << std::endl;
		nums.push_back(n);
		nums.push_back(a);
		nums.push_back(b);
	}
	calc_sequance();
	calc_factorials();
	calc_nCk();
	
	for (int i = 0; i < t; i++) {
		int n = nums[3 * i + 0];
		int A = nums[3 * i + 1];
		int B = nums[3 * i + 2];
		int a = min(A, B);
		int b = max(A, B);
		//std::cout << n << " " << a << " " << b<<" "<<factorials[n]<<" "<<choose[n-a-b][n]<<" "<<sequance[a][b]<<" "<<res << std::endl;

		long long res = (factorials[n] * choose[n][n-a-b] * max(1,sequance[max(1,a+b-1)][max(1,a)]))%MOD;
		if ((a == 0 && b != 0) || (a+b>n)) {
			res = 0;
		}
		//std::cout << n << " " << a << " " << b << " " << factorials[n] << " " << choose[n][n-a-b] << " " << sequance[max(1,a+b-1)][max(1,a)] << " " << res << std::endl;

		std::cout << res << "\n";
	}
}

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:

input
841
19 3 12
19 19 13
19 7 13
20 11 15
...

correct output
40291066
0
0
0
0
...

user output
-124396943
0
0
0
0
...

Test 4

Group: 4, 5

Verdict:

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
-390424387
0
-447848399
...

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
-452882793
936946919
-639431074
709283884
-263211153
...