Submission #1312807

#TimeUsernameProblemLanguageResultExecution timeMemory
1312807boclobanchatKangaroo (CEOI16_kangaroo)C++20
0 / 100
0 ms332 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2025;
const long long mod=1e9+7;
long long dp[MAXN][MAXN];
long long solve(int n,int s,int f,int a,int b,bool ck)
{
	for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j]=0;
	dp[0][0]=1;
	for(int i=1;i<=n;i++) if(i==s)
	{
		for(int j=1;j<=a;j++) dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;
	}
	else if(i==f)
	{
		if((!ck)^(n%2==0)) for(int j=0;j<=a;j++) dp[i][j]=(dp[i][j]+dp[i-1][j]*max(0,j-(i-j-1)))%mod;
		else for(int j=1;j<=a;j++) dp[i][j]=(dp[i][j]+dp[i-1][j-1]*max(0,b-i+j-(a-j-(i<s))))%mod;
	}
	else
	{
		for(int j=1;j<=a;j++) dp[i][j]=(dp[i][j]+dp[i-1][j-1]*max(0,b-i+j-(a-j-(i<s))))%mod;
		for(int j=0;j<=a;j++) dp[i][j]=(dp[i][j]+dp[i-1][j]*max(0,j-(i-j-1)))%mod;
	}
	return dp[n][a];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,s,f;
	cin>>n>>s>>f;
	if(s>f) swap(s,f);
	cout<<(solve(n,s,f,n/2,(n-1)/2,false)+solve(n,s,f,n/2,(n-1)/2,true))%mod;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...