제출 #604721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604721		CSQ31	캥거루 (CEOI16_kangaroo)	C++17	100 / 100	91 ms	125824 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll dp[2][2][2001][2001];
const int MOD = 1e9+7;
int n,s,e;
ll solve(int i,ll cnt,int lf,int rg){
	if(cnt<0)return 0;
	if(dp[lf][rg][i][cnt] != -1)return dp[lf][rg][i][cnt];	
	if(i==n)return (!cnt && lf && rg);
	ll res = 0;
	if(i != s && i != e){
		if(i==n-1)res+=solve(i+1,cnt,lf,rg);
		else{
			res+=solve(i+1,cnt+1,lf,rg); //single cc , > s <  
		    res+=solve(i+1,cnt-1,lf,rg) * 1LL *(cnt) * 1LL * (cnt-1)%MOD; //merge cc , < s > 
			if(lf)res+=solve(i+1,cnt-1,lf,rg) * 1LL * cnt;
			if(rg)res+=solve(i+1,cnt-1,lf,rg) * 1LL * cnt;
		}
	}
	if(i==s){
		if(i==n-1)res+=solve(i+1,cnt,1,rg);
		else{
			res+=solve(i+1,cnt,1,rg); //s < 
			res+=solve(i+1,cnt-1,1,rg) * 1LL * cnt; //s > ... < 
		}
	}
	if(i==e){
		if(i==n-1)res+=solve(i+1,cnt,lf,1);
		else{
			res+=solve(i+1,cnt,lf,1); //s < 
			res+=solve(i+1,cnt-1,lf,1) * 1LL * cnt; //s > ... < 
		}
	}
	res%=MOD;
	return dp[lf][rg][i][cnt] = res;
}
int main()
{
	cin>>n>>s>>e;
	s--;
	e--;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			for(int k=0;k<4;k++){
				dp[k&1][k/2][i][j] = -1;
				
			}	
		}
	}
	/*
	int ans = 0;
	vector<int>v;
	for(int i=0;i<n;i++)v.push_back(i);
	while(true){
		bool ok = 1;
		if(v[0] != s || v[n-1] != e)ok = 0;
		for(int i=0;i+2<n;i++){
			if(v[i] < v[i+1] && v[i+1] < v[i+2])ok = 0;
			if(v[i] > v[i+1] && v[i+1] > v[i+2])ok = 0;
		}
		ans+=ok;
		if(!next_permutation(v.begin(),v.end()))break;
	}
	cout<<ans<<'\n';
	* */
	cout<<solve(0,0,0,0);
}

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