Submission #4029038

---

Source Code Expand

#include<bits/stdc++.h>
#define N (2009)
#define MOD (1000000007)
using namespace std;

int n,k,ans,f[N][N],s[N];

int main()
{
	cin>>n>>k;
	if (k==1) {puts("1"); return 0;}
	for (int i=2; i<=n; ++i) f[1][i]=1;
	for (int i=n; i>=1; --i) s[i]=s[i+1]+f[1][i];
	for (int i=2; i<=k-1; ++i)
	{
		for (int j=1; j<=n-i+1; ++j) f[i][j]=s[j];
		s[n]=f[i][n];
		for (int j=n; j>=1; --j) s[j]=(s[j+1]+f[i][j])%MOD;
	}
	for (int i=2; i<=n; ++i) (ans+=f[k-1][i])%=MOD;
	for (int i=1; i<=n-k-1; ++i) (ans*=2)%=MOD; 
	cout<<ans<<endl;
}

Submission Info

Judge Result