Submission #1281040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281040		ridarfx	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	34 ms	31708 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
const long long INF = 1e18;
const long long mxN = 2005;
const long long MOD = 1e9+7; 
const long long SQRT = 500;
long long dp[mxN][mxN];
long long modadd(long long a, long long b){
	return ((a%MOD)+(b%MOD))%MOD;
}
long long modmult(long long a, long long b){
	return ((a%MOD)*(b%MOD))%MOD;
}
void solve(){
	long long n,a,b;
	cin >> n >> a >> b;
	dp[1][1]=1;
	for(int i=2; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(i==a || i==b){
				dp[i][j]=modadd(dp[i-1][j-1],dp[i-1][j]);
			}
			else{
				dp[i][j]=modadd(modmult(dp[i-1][j-1],(j - (i>a) - (i>b))), modmult(dp[i-1][j+1],j));
			}
		}
	}
	cout << dp[n][1] << endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long t=1; //cin >> t;
    while(t--){
        solve();
    }
}

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