Submission #1839955

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int MOD = 1e9+7;

int add(int a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}

int pow2[2111];
int dp[2111][2111];
int sum[2111][2111];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	pow2[0]=1; for(int i=1;i<=2011;i++){pow2[i]=add(pow2[i-1],pow2[i-1]);}
	int n,k; cin>>n>>k;
	if(n==1)
	{
		cout<<1<<'\n';
		return 0;
	}
	int coeff=(k<n?pow2[n-k-1]:1);
	for(int i=1;i<=n-1;i++) dp[0][i]=1;
	for(int i=1;i<k;i++)
	{
		for(int j=n-i-1;j>=(i==n-1?0:1);j--)
		{
			if(j==n-i-1) dp[i][j]=dp[i-1][j+1];
			else dp[i][j]=dp[i][j+1];
			dp[i][j]=add(dp[i][j],dp[i-1][j]);
		}
	}
	int ans=dp[k-1][(k==n?0:1)];
	ans=mult(ans,coeff);
	cout<<ans<<'\n';
}

Submission Info

Judge Result