fork(1) download
copy 
  1. //satyaki3794
  2. #include <bits/stdc++.h>
  3. #define ff first
  4. #define ss second
  5. #define pb push_back
  6. #define MOD (1000000007LL)
  7. #define LEFT(n) (2*(n))
  8. #define RIGHT(n) (2*(n)+1)
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12. typedef pair<int, int> ii;
  13. typedef pair<int, ii> iii;
  14.  
  15. ll pwr(ll base, ll p, ll mod = MOD){
  16. ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
  17. }
  18.  
  19.  
  20. ll gcd(ll a, ll b){
  21.     if(b == 0)  return a;
  22.     return gcd(b, a%b);
  23. }
  24.  
  25.  
  26.  
  27. int n, k;
  28. ll DP[2002][2002][2], ways[2002];
  29.  
  30.  
  31. ll dp(int i, int left, bool ok){
  32. 	int used = n-i  - left;
  33. 	if(left < 0)	return 0;
  34. 	if(used > k)	return 0;
  35. 	if(i == 1 && used != k){
  36. 		ll ans = 0;
  37. 		if(left > 0 && ok)
  38. 			ans = dp(1, left-1, true);
  39. // cout<<"dp "<<i<<" "<<left<<" "<<ok<<" returns "<<ans<<endl;
  40. 		return ans;
  41. 	}
  42. 	if(used == k || i == 1){
  43. // cout<<"dp "<<i<<" "<<left<<" "<<ok<<" returns 1"<<endl;
  44. 		return 1;
  45. 	}
  46. 	ll &ans = DP[i][left][ok];
  47. 	if(ans != -1)	return ans;
  48.  
  49. 	ans = dp(i-1, left, true) + dp(i-1, left+1, false);
  50. 	ans %= MOD;
  51. 	if(left > 0 && ok){
  52. 		ans += dp(i, left-1, true);
  53. 		ans %= MOD;
  54. 	}
  55. // cout<<"dp "<<i<<" "<<left<<" "<<ok<<" returns "<<ans<<endl;
  56. 	return ans;
  57. }
  58.  
  59.  
  60. int main(){
  61.  
  62.     ios_base::sync_with_stdio(0);
  63.     cin.tie(0);
  64.  
  65.     cin>>n>>k;
  66.  
  67.     ways[0] = ways[1] = 1;
  68.     for(int i=2;i<=n;i++)
  69.     	ways[i] = (ways[i-1] * 2) % MOD;
  70.  
  71.     memset(DP, -1, sizeof(DP));
  72.     k--;
  73.     ll ans = (dp(n, 0, false) * ways[n-k-1]) % MOD;
  74.     cout<<ans;
  75.     return 0;
  76. }
  77.  
  78.  
Success #stdin #stdout 0.09s 66112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Gn8oZp
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!