Submission #1084114

---

Source Code Expand

//satyaki3794
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}
 

ll gcd(ll a, ll b){
    if(b == 0)  return a;
    return gcd(b, a%b);
}



int n, k;
ll DP[2002][2002][2], ways[2002];


ll dp(int i, int left, bool ok){
	int used = n-i  - left;
	if(left < 0)	return 0;
	if(used > k)	return 0;
	if(i == 1 && used != k){
		ll ans = 0;
		if(left > 0 && ok)
			ans = dp(1, left-1, true);
// cout<<"dp "<<i<<" "<<left<<" "<<ok<<" returns "<<ans<<endl;
		return ans;
	}
	if(used == k || i == 1){
// cout<<"dp "<<i<<" "<<left<<" "<<ok<<" returns 1"<<endl;
		return 1;
	}
	ll &ans = DP[i][left][ok];
	if(ans != -1)	return ans;

	ans = dp(i-1, left, true) + dp(i-1, left+1, false);
	ans %= MOD;
	if(left > 0 && ok){
		ans += dp(i, left-1, true);
		ans %= MOD;
	}
// cout<<"dp "<<i<<" "<<left<<" "<<ok<<" returns "<<ans<<endl;
	return ans;
}


int main(){
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>k;

    ways[0] = ways[1] = 1;
    for(int i=2;i<=n;i++)
    	ways[i] = (ways[i-1] * 2) % MOD;

    memset(DP, -1, sizeof(DP));
    k--;
    ll ans = (dp(n, 0, false) * ways[n-k-1]) % MOD;
    cout<<ans;
    return 0;
}

Submission Info

Judge Result