Ncr
(lib/util/ncr.hpp)

• View this file on GitHub
• Last update: 2020-08-11 13:42:23+09:00
• Include: #include "lib/util/ncr.hpp"

Depends on

• Mint (lib/util/mint.hpp)

Code

#pragma once
#include "../../lib/util/mint.hpp"
#define MAXN 10000010
md_tmp class Ncr{
	lint m;
public:
	mint fa[MAXN],rfa[MAXN];
	Ncr(lint n):m(n){
		fa[0]=1;
		for(int i=1; i<m; ++i)fa[i]=(fa[i-1]*i);
		rfa[m-1]=mint(1)/fa[m-1];
		for(int i=m-2; i>=0; --i)rfa[i]=rfa[i+1]*(i+1);
	}
	inline mint ncr(lint n,lint r){ if(n<r||n<0||r<0)return 0m; return(fa[n]*rfa[r]*rfa[n-r]); }
};
Ncr<> c(MAXN);
#undef MAXN

/*
* @title Ncr
*/

#line 2 "lib/util/mint.hpp"
#define md_tmp template<uint_fast64_t md=mod>
md_tmp class modint{
	using u64=uint_fast64_t;

public:
	u64 a;

	constexpr modint(const lint x=0) noexcept: a((x+md)%md){}
	constexpr u64 &value() noexcept{ return a; }
	constexpr const u64 &value() const noexcept{ return a; }
	constexpr modint operator+(const modint rhs) const noexcept{
		return modint(*this)+=rhs;
	}
	constexpr modint operator-(const modint rhs) const noexcept{
		return modint(*this)-=rhs;
	}
	constexpr modint operator*(const modint rhs) const noexcept{
		return modint(*this)*=rhs;
	}
	constexpr modint operator^(const lint rhs) const noexcept{
		return modint(*this)^=rhs;
	}
	constexpr modint operator/(const modint rhs) const noexcept{
		return modint(*this)/=rhs;
	}
	constexpr modint &operator+=(const modint rhs) noexcept{
		a+=rhs.a;
		if(a>=md)a-=md;
		return *this;
	}
	constexpr modint &operator-=(const modint rhs) noexcept{
		if(a<rhs.a)a+=md;
		a-=rhs.a;
		return *this;
	}
	constexpr modint &operator*=(const modint rhs) noexcept{
		a=a*rhs.a%md;
		return *this;
	}
	constexpr modint &operator^=(const lint rhs) noexcept{
		if(!rhs)return *this = 1;
		u64 exp=rhs-1;
		modint base=a;
		while(exp){
			if(exp&1)*this*=base;
			base*=base;
			exp>>=1;
		}
		return *this;
	}
	constexpr modint &operator/=(const modint rhs) noexcept{
		a=(*this*(rhs^(md-2))).a;
		return *this;
	}
};
md_tmp istream& operator>>(istream& os,modint<md>& m){
	os>>m.a,m.a%=md;
	return os;
}
md_tmp ostream& operator<<(ostream& os,const modint<md>& m){
	return os<<m.a;
}
using mint = modint<>;
//#ifndef _AOJ_
//mint operator""m(unsigned long long n){ return mint(n); }
//#endif

/*
* @title Mint
* @see https://noshi91.hatenablog.com/entry/2019/03/31/174006
*/
#line 3 "lib/util/ncr.hpp"
#define MAXN 10000010
md_tmp class Ncr{
	lint m;
public:
	mint fa[MAXN],rfa[MAXN];
	Ncr(lint n):m(n){
		fa[0]=1;
		for(int i=1; i<m; ++i)fa[i]=(fa[i-1]*i);
		rfa[m-1]=mint(1)/fa[m-1];
		for(int i=m-2; i>=0; --i)rfa[i]=rfa[i+1]*(i+1);
	}
	inline mint ncr(lint n,lint r){ if(n<r||n<0||r<0)return 0m; return(fa[n]*rfa[r]*rfa[n-r]); }
};
Ncr<> c(MAXN);
#undef MAXN

/*
* @title Ncr
*/

Back to top page