fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Modular Combinatorics
  4. //
  5. //  Created by Himanshu on 18/02/22.
  6. //
  7.  
  8. #include <iostream>
  9. #define p 1000000007
  10. using namespace std;
  11. typedef long long ll;
  12.  
  13. void precompute (int n, ll fact[], ll inv[], ll invFact[]) {
  14.     fact[0] = 1;
  15.  
  16.     for (int i=1; i<= n; i++) {
  17.         fact[i] = (fact[i-1]*i)%p;
  18.     }
  19.  
  20.     inv[1] = 1;
  21.     for (int i=2; i<= n; i++) {
  22.         inv[i] = ((p - (p/i))*inv[p%i])%p;
  23.     }
  24.  
  25.     invFact[0] = invFact[1] = 1;
  26.  
  27.     for (int i=2; i<= n; i++) {
  28.         invFact[i] = (invFact[i-1]*inv[i])%p;
  29.     }
  30. }
  31.  
  32. ll computeCombinatorics (int n, int r, ll fact[], ll inv[], ll invFact[]) {
  33.     ll ans = (((fact[n]*invFact[r])%p)*(invFact[n-r]%p))%p;
  34.     return ans;
  35. }
  36.  
  37.  
  38. int main (int argc, const char * argv[]) {
  39.     int n = 100000;
  40.     int r = 500;
  41.  
  42.     ll *fact = new ll[n]();
  43.     ll *inv = new ll[n]();
  44.     ll *invFact = new ll[n]();
  45.  
  46.     precompute(n, fact, inv, invFact);
  47.     cout<<computeCombinatorics(n, r, fact, inv, invFact)<<endl;
  48.  
  49.     return 0;
  50. }
  51.  
Success #stdin #stdout 0.01s 6024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
115855765
https://ideone.com/Nmzddv
language:
C++14 (gcc 8.3)
created:
2 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!