Kortit II

#include <iostream>
#include <vector>
 
const int MAX = 2100;
 
long long sequance[MAX][MAX]; // n,r
long long factorials[MAX];
long long choose[MAX][MAX];
 
const int MOD = 1000000007;
 
long long min(long long a, long long b) {
	if (a < b) {
		return a;
	}
	return b;
}
 
long long max(long long a, long long b) {
	if (a < b) {
		return b;
	}
	return a;
}
 
void calc_sequance() {
	sequance[0][1] = 0;
	for (int i = 1; i < MAX; i++) {
		sequance[i][i] = 1;
		sequance[i-1][i] = 0;
	}
	for (int i = 1; i < MAX; i++) {
		sequance[i][1] = 1;
		sequance[i][0] = 0;
	}
	for (int r = 2; r < MAX-1;r++) {
		for (int n = r; n < MAX-1; 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 < MAX-1; i++) {
		factorials[i + 1] = (factorials[i] * (i + 1))%MOD;
	}
}
 
void calc_nCk() {
	for (int n = 0; n < MAX; n++) {
		choose[n][0] = 1;
		//choose[0][n] = 1;
	}
	for (int n = 0; n < MAX-1; n++) {
		for (int k = 0; k < MAX-1; 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;
		if ((a == 0 && b != 0) || (a + b > n)) {
			res = 0;
		}
		else {
			res = (((factorials[n] * choose[n][n - a - b]) % MOD) * max(1, sequance[a + b - 1][a])) % MOD;
		}
		//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 1

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 3, 4, 5

Verdict: ACCEPTED

Test 4

Group: 4, 5

Verdict: ACCEPTED

Test 5

Group: 5

Verdict: ACCEPTED

Test 6

Group: 5

Verdict: ACCEPTED