Submission #110564

#	Time	Username	Problem	Language	Result	Execution time	Memory
110564		gumball	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	149 ms	32408 KiB

kangaroo

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,S,T,d[2020][2020],mo=1e9+7;
ll depe(ll aa,ll bb)
{
	if(aa==(n+1)&&bb==1)return 1;
	if(aa==(n+1))return 0;
	if(bb<0)return 0;
	ll ret=d[aa][bb];
	if(ret!=-1)return ret;
	ret=0;
	ll ujg=0;
	if(aa>S)ujg++;
	if(aa>T)ujg++;
	if(aa==S||aa==T)
	{
		ret=(depe(aa+1,bb+1)+depe(aa+1,bb))%mo;
	}	
	else
	{	
		ret=(ret+depe(aa+1,bb+1)*(bb+1-ujg))%mo;
		ret=(ret+depe(aa+1,bb-1)*(bb-1))%mo;
	}
	return d[aa][bb]=ret;
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>S>>T;
	memset(d,-1,sizeof(d));
	if(n==2)cout<<1<<"\n";
	else
		cout<<depe(1,0)<<"\n";
}	

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