階乗、nPr、nCr
(math/factorial.hpp)

• View this file on GitHub
• Last update: 2021-04-15 20:33:39+09:00
• Include: #include "math/factorial.hpp"

Depends on

• mod int (math/modint.hpp)

Code

// @title 階乗、nPr、nCr
#include <vector>
#include "modint.hpp"

template <int mod>
struct Factorial {
  using mint = ModInt<mod>;
  std::vector<mint> Fact, Finv;
public:
  Factorial(int _n): Fact(_n+1), Finv(_n+1) {
      Fact[0]=mint(1); for (int i = 0; i < _n; ++i) Fact[i+1]=Fact[i]*(i+1);
      Finv[_n]=mint(1)/Fact[_n]; for (int i = _n; i > 0; --i) Finv[i-1]=Finv[i]*i;
  }
  mint fact(int n,bool inv=0) { if (inv) return Finv[n]; else return Fact[n]; }
  mint nPr(int n,int r){ if (n<0||n<r||r<0) return mint(0); else return Fact[n]*Finv[n-r]; }
  mint nCr(int n,int r){ if (n<0||n<r||r<0) return mint(0); else return Fact[n]*Finv[r]*Finv[n-r]; }
};

using factorial = Factorial<MOD10>;
using factorial99 = Factorial<MOD99>;

#line 1 "math/factorial.hpp"
// @title 階乗、nPr、nCr
#include <vector>
#line 1 "math/modint.hpp"
// @title mod int
#include <iostream>
using ll = long long;

#ifdef MUTABLE
int mod;
#else
template<int mod>
#endif
struct ModInt {
  int val;
  ModInt inv() const{
    int tmp,a=val,b=mod,x=1,y=0;
    while(b)tmp=a/b,a-=tmp*b,std::swap(a,b),x-=tmp*y,std::swap(x,y);
    return ModInt(x);
  }
  ModInt():val(0){}
  ModInt(ll x){if((val=x%mod)<0)val+=mod;}
  ModInt pow(ll t){ModInt res=1,b=*this; while(t){if(t&1)res*=b;b*=b;t>>=1;}return res;}
  ModInt& operator+=(const ModInt& x){if((val+=x.val)>=mod)val-=mod;return *this;}
  ModInt& operator-=(const ModInt& x){if((val+=mod-x.val)>=mod)val-=mod; return *this;}
  ModInt& operator*=(const ModInt& x){val=(ll)val*x.val%mod; return *this;}
  ModInt& operator/=(const ModInt& x){return *this*=x.inv();}
  bool operator==(const ModInt& x) const{return val==x.val;}
  bool operator!=(const ModInt& x) const{return val!=x.val;}
  bool operator<(const ModInt& x) const{return val<x.val;}
  bool operator<=(const ModInt& x) const{return val<=x.val;}
  bool operator>(const ModInt& x) const{return val>x.val;}
  bool operator>=(const ModInt& x) const{return val>=x.val;}
  ModInt operator+(const ModInt& x) const{return ModInt(*this)+=x;}
  ModInt operator-(const ModInt& x) const{return ModInt(*this)-=x;}
  ModInt operator*(const ModInt& x) const{return ModInt(*this)*=x;}
  ModInt operator/(const ModInt& x) const{return ModInt(*this)/=x;}
  friend std::ostream& operator<<(std::ostream& os, const ModInt& mi) { os << mi.val; return os; }
  static int get_mod() { return mod; }
};

constexpr int MOD10 = 1000000007;
constexpr int MOD99 =  998244353;
#ifndef MUTABLE
using modint = ModInt<MOD10>;
using modint99 = ModInt<MOD99>;
#endif
#line 4 "math/factorial.hpp"

template <int mod>
struct Factorial {
  using mint = ModInt<mod>;
  std::vector<mint> Fact, Finv;
public:
  Factorial(int _n): Fact(_n+1), Finv(_n+1) {
      Fact[0]=mint(1); for (int i = 0; i < _n; ++i) Fact[i+1]=Fact[i]*(i+1);
      Finv[_n]=mint(1)/Fact[_n]; for (int i = _n; i > 0; --i) Finv[i-1]=Finv[i]*i;
  }
  mint fact(int n,bool inv=0) { if (inv) return Finv[n]; else return Fact[n]; }
  mint nPr(int n,int r){ if (n<0||n<r||r<0) return mint(0); else return Fact[n]*Finv[n-r]; }
  mint nCr(int n,int r){ if (n<0||n<r||r<0) return mint(0); else return Fact[n]*Finv[r]*Finv[n-r]; }
};

using factorial = Factorial<MOD10>;
using factorial99 = Factorial<MOD99>;

Back to top page