cpp/math/combination.cpp

• View this file on GitHub
• Last update: 2023-07-24 12:50:52+09:00

Required by

• cpp/geometry/two-points-distance.cpp

Verified with

• cpp/z_test/yukicoder-0117.test.cpp

Code

struct Combination {
  long long n_max;
  int mod;
  vector<long long> fac, inv, finv;
  Combination(int n, int mod):n_max(n), mod(mod), fac(n+1,1), inv(n+1,1), finv(n+1,1){
    for(int i = 2; n > i; i++){
      fac[i] = (fac[i-1]*i)%mod;
      inv[i] = mod-((inv[mod%i]*(mod/i))%mod);
      finv[i] = (finv[i-1]*inv[i])%mod;
    }
  }

  long long C(int n, int r){
    if(n < r)return 0;
    if(n > n_max)return 0;
    return (((fac[n]*finv[r])%mod)*finv[n-r])%mod;
  }

  long long P(int n, int r){
    if(n < r)return 0;
    if(n > n_max)return 0;
    return (fac[n]*finv[n-r])%mod;
  }

  long long H(int n, int r){
    if(n==0 && r==0)return 1;
    return C(n+r-1, r);
  }
};

#line 1 "cpp/math/combination.cpp"
struct Combination {
  long long n_max;
  int mod;
  vector<long long> fac, inv, finv;
  Combination(int n, int mod):n_max(n), mod(mod), fac(n+1,1), inv(n+1,1), finv(n+1,1){
    for(int i = 2; n > i; i++){
      fac[i] = (fac[i-1]*i)%mod;
      inv[i] = mod-((inv[mod%i]*(mod/i))%mod);
      finv[i] = (finv[i-1]*inv[i])%mod;
    }
  }

  long long C(int n, int r){
    if(n < r)return 0;
    if(n > n_max)return 0;
    return (((fac[n]*finv[r])%mod)*finv[n-r])%mod;
  }

  long long P(int n, int r){
    if(n < r)return 0;
    if(n > n_max)return 0;
    return (fac[n]*finv[n-r])%mod;
  }

  long long H(int n, int r){
    if(n==0 && r==0)return 1;
    return C(n+r-1, r);
  }
};

Back to top page