fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3.  
  4. typedef long long ll;  
  5.  
  6. // Nhập vào n, k. In ra nCk mod 10^9 + 7.  
  7.  
  8. // nCk = n! / [(n - k)! * k!]
  9.  
  10. const int N = 1e6 + 5;  
  11. const int MOD = 1e9 + 7;  
  12.  
  13. ll fact[N], inv_fact[N];  
  14.  
  15. ll binpow(ll a, ll b) {
  16. 	ll ans = 1;  
  17. 	for (; b > 0; b >>= 1) {
  18. 		if (b & 1) ans = ans * a % MOD;    
  19. 		a = a * a % MOD; 
  20. 	}
  21. 	return ans; 
  22. }
  23.  
  24. ll inv(int x) {
  25. 	return binpow(x, MOD - 2);   
  26. }
  27.  
  28. void precompute() {
  29. 	fact[0] = 1;  
  30. 	// i! = (i - 1)! * i  
  31. 	for (int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;   
  32.  
  33. 	inv_fact[N - 1] = inv(fact[N - 1]);   
  34. 	for (int i = N - 2; i >= 0; i--) inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;   
  35. }
  36.  
  37. ll nCk(int n, int k) { // n >= k 
  38. 	if (n < k) return 0;   
  39. 	return fact[n] * inv_fact[n - k] % MOD * inv_fact[k] % MOD;  
  40. }
  41.  
  42. int main() {
  43. 	ios::sync_with_stdio(0); cin.tie(0);  
  44. 	int t; cin >> t;
  45.  
  46. 	precompute(); // O(n) 
  47.  
  48. 	while (t--) {
  49. 		int n, k; 
  50. 		cin >> n >> k;  
  51.  
  52. 		cout << nCk(n, k) << '\n'; // O(1) 
  53. 	}
  54. }
Success #stdin #stdout 0.02s 19120KB
comments (?)
stdin
copy 
5
6 2
3 4
3 3
50 8 
26 4
stdout
copy 
15
0
1
536878650
14950
https://ideone.com/sEPq61
language:
C++14 (gcc 8.3)
created:
1 year 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!