Submission #1288921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288921		euthymia2606	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	15 ms	14176 KiB

kangaroo

#include <bits/stdc++.h> 

using namespace std;  

typedef long long ll;  
typedef pair<int, int> ii;  

const int INF = 1e9;  
const ll LINF = 1e18;  

const int N = 2e3 + 5; 
const int MOD = 1e9 + 7;  

int n, cs, cf;  
int dp[N][N];

void add(int& a, int b) {
	a += b;
	if (a >= MOD) a -= MOD; 
}

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(nullptr); 	
	cin >> n >> cs >> cf;  

	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			if (i + 1 == cs || i + 1 == cf) {
				add(dp[i + 1][j + 1], dp[i][j]); 
				if (j > 0) add(dp[i + 1][j], dp[i][j]);
				continue;
			}
			add(dp[i + 1][j + 1], 1ll * dp[i][j] * (j - 1 + (i < cs) + (i < cf)) % MOD); 
			if (j > 1) add(dp[i + 1][j - 1], 1ll * dp[i][j] * (j - 1) % MOD);
		}
	}

	cout << dp[n][1] << '\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49