fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long memo[65][65][2];
  5. int n,k;
  6.  
  7. long long DP(int index,int cnt,int found)
  8. {
  9. 	long long &res = memo[index][cnt][found];
  10. 	if(res==-1)
  11. 	{
  12. 		res = 0;
  13. 		if(index==n)
  14. 		{
  15. 			if(found)
  16. 				res = 1;
  17. 		}
  18. 		else
  19. 		{
  20. 			if(cnt+1>=k)
  21. 				res += DP(index+1,cnt+1,true);
  22. 			else
  23. 				res += DP(index+1,cnt+1,found);
  24. 			res += DP(index+1,0,found);
  25. 		}
  26. 	}
  27. 	return res;
  28. }
  29.  
  30. long long gcd(long long a,long long b)
  31. {
  32. 	if(b==0)
  33. 		return a;
  34. 	else
  35. 		return gcd(b,a%b);
  36. }
  37.  
  38. int main()
  39. {
  40. 	for(int i=0;i<65;++i)
  41. 		for(int j=0;j<65;++j)
  42. 			for(int k=0;k<2;++k)
  43. 				memo[i][j][k] = -1;
  44. 	cin >> n >> k;
  45. 	long long ans = DP(0,0,0),den = (1LL<<n),m;
  46. 	//cout << ans << endl;
  47. 	m = gcd(ans,den);
  48. 	cout << ans/m << "/" << den/m;
  49. }
Success #stdin #stdout 0s 3364KB
comments (?)
stdin
copy 
5 2
stdout
copy 
19/32
https://ideone.com/ipZyDb
language:
C++ (gcc 8.3)
created:
9 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!