Submission #4029106

---

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;
	f[0][n+1]=1; s[n+1]=1;
	for (int i=n; i>=1; --i) s[i]=s[i+1]+f[0][i];
	for (int i=1; i<=k-1; ++i)
	{
		for (int j=1; j<=n-i+1; ++j) f[i][j]=s[j];
		s[n+1]=f[i][n+1];
		for (int j=n; j>=1; --j) s[j]=(s[j+1]+f[i][j])%MOD;
	}
	for (int i=2; i<=n+1; ++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