fork(5) download
copy 
  1. /*
  2. 	computing binomial coefficients i.e. N choose R using O(n) precomputation.
  3. 	use this for large value of N and whem (NchooseR)%prime is used;
  4. */
  5. //by Tanmay Chaudhari
  6. #ifdef _MSC_VER
  7. #define _CRT_SECURE_NO_WARNINGS
  8. #endif
  9. //#pragma comment(linker, "/STACK:66777216")
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12.  
  13. #define si(a)				scanf("%d",&a)
  14. #define sl(a)				scanf("%lld",&a)
  15. #define pi(a)				printf("%d\n",a)
  16. #define pl(a)				printf("%lld\n",a)
  17.  
  18. typedef long long			LL;
  19. typedef vector<int>			vi;
  20. typedef pair<int, int>		ii;
  21. typedef vector<vi>			vvi;
  22. typedef vector<ii>			vii;
  23.  
  24. #define SET(a,b)			memset(a,b,sizeof(a))	
  25. #define forall(i,a,b)		for(int i=a; i<b; i++)
  26. #define forrev(i,a,b)		for(int i=a; i>=b; i--)
  27. #define forr(it,container)  for(auto it=container.begin(); it!=container.end(); it++)
  28. #define w(t)				int t;si(t);while(t--)
  29.  
  30. #define TRACE
  31.  
  32. #ifdef TRACE
  33. #define trace1(x)                cerr << #x << ": " << x << endl;
  34. #define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  35. #define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  36. #define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  37. #define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  38. #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  39.  
  40. #else
  41.  
  42. #define trace1(x)
  43. #define trace2(x, y)
  44. #define trace3(x, y, z)
  45. #define trace4(a, b, c, d)	
  46. #define trace5(a, b, c, d, e)
  47. #define trace6(a, b, c, d, e, f)
  48.  
  49. #endif
  50.  
  51. const int MOD = 1e9 + 7;
  52. #define N 2123456
  53.  
  54. LL fac[N], ifac[N];
  55.  
  56. LL PowerMod(LL a, LL n){
  57. 	LL ret = 1;
  58. 	while (n){
  59. 		if (n & 1){
  60. 			ret *= a;
  61. 			ret %= MOD;
  62. 		}
  63. 		a *= a;
  64. 		a %= MOD;
  65. 		n /= 2;
  66. 	}
  67. 	return ret;
  68. }
  69.  
  70. inline void precompute(){
  71. 	int i;
  72. 	fac[0] = 1;
  73. 	for (i = 1; i < N; i++){
  74. 		fac[i] = (i * fac[i - 1]) % MOD;
  75. 	}
  76. 	ifac[N - 1] = PowerMod(fac[N - 1], MOD - 2);
  77. 	for (i = N - 2; i >= 0; i--){
  78. 		ifac[i] = ((i + 1) * ifac[i + 1]) % MOD;
  79. 	}
  80. }
  81.  
  82. LL com(int n, int r){
  83. 	LL ret = fac[n];
  84. 	ret *= ifac[r];
  85. 	ret %= MOD;
  86. 	ret *= ifac[n - r];
  87. 	ret %= MOD;
  88. 	return ret;
  89. }
  90.  
  91. int main()
  92. {
  93. 	//freopen("input.txt","r",stdin);
  94. 	//freopen("output.txt","w",stdout);
  95. 	precompute();
  96. 	pl(com(4892,231));
  97. 	return 0;
  98. }
Success #stdin #stdout 0.19s 36640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
170656587
https://ideone.com/Bf9etl
language:
C++14 (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!