fork(2) download
copy 
  1. //Computing Binomial Coefficients i.e. N choose R using dynamic programming!
  2. /*
  3. using the recurrent formula	nCr=(n-1)C(r)+(n-1)C(r-1)
  4. we can use dynamic programming type approach to precompute all the binomial coefficients in O(n^2) and answer queries in O(1)
  5. use this method when n<=5000 only.
  6. also use this method when nCr%non-prime is required.
  7. */
  8. //by Tanmay Chaudhari
  9. #ifdef _MSC_VER
  10. #define _CRT_SECURE_NO_WARNINGS
  11. #endif
  12. //#pragma comment(linker, "/STACK:66777216")
  13. #include <bits/stdc++.h>
  14. using namespace std;
  15.  
  16. #define si(a)				scanf("%d",&a)
  17. #define sl(a)				scanf("%lld",&a)
  18. #define pi(a)				printf("%d\n",a)
  19. #define pl(a)				printf("%lld\n",a)
  20.  
  21. typedef long long			ll;
  22. typedef vector<int>			vi;
  23. typedef pair<int, int>		ii;
  24. typedef vector<vi>			vvi;
  25. typedef vector<ii>			vii;
  26.  
  27. #define SET(a,b)			memset(a,b,sizeof(a))	
  28. #define forall(i,a,b)		for(int i=a; i<b; i++)
  29. #define forrev(i,a,b)		for(int i=a; i>=b; i--)
  30. #define forr(it,container)  for(auto it=container.begin(); it!=container.end(); it++)
  31. #define w(t)				int t;si(t);while(t--)
  32.  
  33. #define TRACE
  34.  
  35. #ifdef TRACE
  36. #define trace1(x)                cerr << #x << ": " << x << endl;
  37. #define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  38. #define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  39. #define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  40. #define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  41. #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  42.  
  43. #else
  44.  
  45. #define trace1(x)
  46. #define trace2(x, y)
  47. #define trace3(x, y, z)
  48. #define trace4(a, b, c, d)	
  49. #define trace5(a, b, c, d, e)
  50. #define trace6(a, b, c, d, e, f)
  51.  
  52. #endif
  53.  
  54. const int MOD = 1e9 + 7;
  55. ll ncr[5005][5005];
  56.  
  57. void precompute()
  58. {
  59. 	int k;
  60. 	for (int i = 0; i < 5001; i++)
  61. 	{
  62. 		ncr[i][0] = ncr[i][i] = 1;
  63. 		k = i >> 1;
  64. 		for (int j = 1; j < k + 1; j++)
  65. 			ncr[i][j] = ncr[i][i - j] = (ncr[i - 1][j] + ncr[i - 1][j - 1]) % MOD;
  66. 	}
  67. }
  68.  
  69. int main()
  70. {
  71. 	//freopen("input.txt","r",stdin);
  72. 	//freopen("output.txt","w",stdout);
  73. 	precompute();
  74. 	pl(ncr[4892][231]);
  75. 	return 0;
  76. }
Success #stdin #stdout 0.36s 199168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
170656587
https://ideone.com/wwE6Py
language:
C++14 (gcc 8.3)
created:
8 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!