fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXN = 100000;
  5. const int MOD = 1000000007;
  6.  
  7. ll fact[MAXN + 1], ifact[MAXN + 1];
  8.  
  9. // Function to compute (base^exp) % MOD using Binary Exponentiation
  10. ll power(ll base, ll exp, ll mod) {
  11.     ll result = 1;
  12.     while (exp > 0) {
  13.         if (exp % 2 == 1) result = (result * base) % mod;
  14.         base = (base * base) % mod;
  15.         exp /= 2;
  16.     }
  17.     return result;
  18. }
  19.  
  20. // Precompute Factorial and Inverse Factorial
  21. void precompute() {
  22.     fact[0] = ifact[0] = 1;
  23.     for (int i = 1; i <= MAXN; i++) {
  24.         fact[i] = (fact[i - 1] * i) % MOD;
  25.     }
  26.     ifact[MAXN] = power(fact[MAXN], MOD - 2, MOD); // Fermat's theorem
  27.     for (int i = MAXN - 1; i >= 1; i--) {
  28.         ifact[i] = (ifact[i + 1] * (i + 1)) % MOD;
  29.     }
  30. }
  31.  
  32. // Compute nCr % MOD
  33. ll nCr(int n, int r) {
  34.     if (r > n || r < 0) return 0;
  35.     return (fact[n] * ifact[r] % MOD) * ifact[n - r] % MOD;
  36. }
  37.  
  38.  
  39. int main() {
  40.     precompute();
  41.     int t, n, r;
  42.     cin >> t;
  43.     while (t--) {
  44.         cin >> n >> r;
  45.         cout << nCr(n, r) << endl;
  46.     }
  47.     return 0;
  48. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Fk0hT3
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

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!