조합의 소수 모듈러 값 빠르게 구하기 (n C m % p)

<참고한 블로그>

https://ryulstory.tistory.com/62

 

<설명>

페르마 소정리에 따르면 p가 소수인 경우

 a^(p-1) = 1 (mod p)  

1/a mod p == a^(p-2)

 

즉 다음을 만족함

(a*b) % p = (a%p) * (b%p) 

(a/b) % p = (a%p) * (b^(p-2) % p)

 

nCk  (mod p) = n! /(k! * (n-k)!) (mod p)

 = (n! mod p) * ((k! * (n-k)!)^(p-2) mod p )

 

다음 두 배열을 전처리해준다. O(n)

fac[x] : x! % MOD 

fac_inv[x] : (x!)^(-1) %MOD

   -> n * inverse(n!) = inverse((n-1)!) 를 이욯

 

O(1)에 nCm % p 를 구할 수 있다.

 

<코드>

const ll MOD = 1e9+7; //반드시 소수여야 한다.

ll fac[MAX], fac_inv[MAX]; //fac, fac_inv %MOD
ll pw(ll x, ll y) {
	if (y == 0) return 1;

	ll ret;
	if (y % 2) ret = (x * pw(x, y - 1))%MOD;
	else {
		ret = pw(x, y / 2);
		ret = (ret * ret) % MOD;
	}
	return ret;
}
void makeFac() {
	fac[0] = 1; 
	for (int i = 1; i < MAX; i++)
		fac[i] = (fac[i - 1] * i) % MOD;

	fac_inv[MAX - 1] = pw(fac[MAX - 1], MOD - 2);
	for (int i = MAX - 2; i >= 0; i--)
		fac_inv[i] = (fac_inv[i + 1] * (i + 1)) % MOD;	
}
ll combination(int x, int y) { // (x C y)%MOD 반환
	if (x == y) return 1;
	if (y == 1) return x;

	ll ret = (fac[x] * fac_inv[x - y]) % MOD;
	ret = (ret * fac_inv[y]) % MOD;
	return ret;
}