Submission #728564

#	Time	Username	Problem	Language	Result	Execution time	Memory
728564		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	34 ms	31828 KiB

kangaroo

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const ll MOD=1e9+7;
ll N,x,y,dp[2005][2005];
int main(){
	cin>>N>>x>>y;
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int i=0;i<=N-1;i++){
		for(int j=0;j<=N-1;j++){
			ll cur=dp[i][j];
			ll e=0;
			if(i>=x){
				e++;
			}
			if(i>=y){
				e++;
			}
			if(i==x-1||i==y-1){
				dp[i+1][j+1]+=cur;
				if(i==N-1&&e==1&&j==1){
					dp[i+1][j]+=cur;
				}
				else{
					dp[i+1][j]+=(j-e)*cur;
				}
				dp[i+1][j+1]%=MOD;
				dp[i+1][j]%=MOD;
			}
			else{
				dp[i+1][j+1]+=cur;
				if(j>0){
					if(i==N-1){
						dp[i+1][j-1]+=cur;
					}
					if(e>0&&(j-e)>0){
						dp[i+1][j-1]+=e*(j-e)*cur;
					}
					if((j-e)>=2){
						dp[i+1][j-1]+=(j-e)*(j-e-1)*cur;
					}
				}
				dp[i+1][j+1]%=MOD;
				dp[i+1][j-1]%=MOD;
			}
		}
	}
	cout<<dp[N][1]<<endl;
}

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