Submission #1222086

#TimeUsernameProblemLanguageResultExecution timeMemory
1222086boclobanchat캥거루 (CEOI16_kangaroo)C++20
51 / 100
2096 ms35400 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2048;
const int mod=1e9+7;
int dp[MAXN][MAXN][2],pref[MAXN][2],suff[MAXN][2],C[MAXN][MAXN];
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);
	C[0][0]=1;
	for(int i=1;i<=n;i++) for(int j=0;j<=i;j++)
	{
		C[i][j]=C[i-1][j];
		if(j) C[i][j]=(C[i][j]+C[i-1][j-1])%mod;
	}
	for(int i=1;i<=n;i++) if(i==1) dp[1][1][0]=dp[1][1][1]=1;
	else
	{
		for(int j=1;j<i;j++) 
		{
			pref[j][0]=(pref[j-1][0]+dp[i-1][j][0])%mod;
			pref[j][1]=(pref[j-1][1]+dp[i-1][j][1])%mod;
		}
		suff[i][0]=suff[i][1]=0;
		for(int j=i-1;j;j--)
		{
			suff[j][0]=(suff[j+1][0]+dp[i-1][j][0])%mod;
			suff[j][1]=(suff[j+1][1]+dp[i-1][j][1])%mod;
		}
		for(int j=1;j<=i;j++)
		{
			if(i%2==0) dp[i][j][0]=pref[j-1][0],dp[i][j][1]=suff[j][1];
			else dp[i][j][0]=suff[j][0],dp[i][j][1]=pref[j-1][1];
		}
	}
	if(f==n) return cout<<dp[n-1][s][0],0;
	int ans=0;
	for(int i=0;i<s;i++) for(int j=0;j<f-s;j++) for(int k=0;k<n-f;k++) ans=(ans+1LL*C[s-1][i]*C[f-s-1][j]%mod*C[n-f-1][k]%mod*dp[i+j+k+1][i+1][0]%mod*dp[n-2-i-j-k][f-i-j-1][0]%mod)%mod;
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...