Submission #51370

#	Time	Username	Problem	Language	Result	Execution time	Memory
51370		spencercompton	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	180 ms	32304 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, cs, cf;
ll mod = 1000000007LL;
ll dp[2001][2001];
ll go(int now, int blocks){
	if(now==n+1){
		if(blocks==1){
			return 1LL;
		}
		return 0LL;
	}
	if(dp[now][blocks]!=-1LL){
		return dp[now][blocks];
	}
	ll ret = 0LL;
	if(now==cs){
		if(now>cf){
			ret = go(now+1,blocks+1);
			if(blocks>1 && now<n){
				 ret += go(now+1,blocks)*(ll)(blocks-1);
			}
			if(now==n){
				ret += go(now+1,blocks);
			}
			ret %= mod;
		}
		else{
			ret = go(now+1,blocks+1);
			if(blocks>=1){
				ret += go(now+1,blocks)*(ll)blocks;
			}
			ret %= mod;
		}
	}
	else if(now==cf){
		if(now>cs){
			ret = go(now+1,blocks+1);
			if(blocks>1 && now<n){
				ret += go(now+1,blocks)*(blocks-1);
			}
			if(now==n){
				ret += go(now+1,blocks);
			}
			ret %= mod;
		}
		else{
			ret = go(now+1,blocks+1);
			if(blocks>=1){
				ret += go(now+1,blocks)*(ll)blocks;
			}
			ret %= mod;
		}
	}
	else{
		ret = go(now+1,blocks+1);
		int cnt = 0;
		if(now>cs){
			cnt++;
		}
		if(now>cf){
			cnt++;
		}
		if(cnt==0){
			//rand and then rand
			if(blocks>=2){
				ret += go(now+1,blocks-1) * ((blocks*(blocks-1))%mod);
				ret %= mod;
			}

		}
		else if(cnt==1){
			//rand and then rand
			if(blocks>=3){
				ret += go(now+1,blocks-1) * (((blocks-2)*(blocks-1))%mod);
				ret %= mod;
			}
			//imp and something
			if(blocks>=2){
				ret += go(now+1,blocks-1) * (blocks-1);
				ret %= mod;
			}

			
		}
		else{
			//rand and then rand
			if(blocks>=4){
				ret += go(now+1,blocks-1) * (((blocks-2)*(blocks-3))%mod);
				ret %= mod;
			}
			//imp and something
			if(blocks>=3){
				ret += 2LL * go(now+1,blocks-1) * (ll)(blocks-2);
				ret %= mod;
			}
			//imp and imp
			if(now==n){
				ret += go(now+1,blocks-1);
				ret %= mod;
			}
		}
	}
	dp[now][blocks] = ret;
	return ret;
}
int main(){
	cin >> n >> cs >> cf;
	for(int a = 0; a<=2000; a++){
		for(int b= 0; b<=2000; b++){
			dp[a][b] = -1LL;
		}
	}
	cout << go(1,0) << endl;

}

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