[분할 정복 단계] 백준 11401번 이항 계수 3

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

출력

 (NK)를 1,000,000,007로 나눈 나머지를 출력한다.

 

페르마의 소정리 

A!/B! % MOD = A! * pow(B! , MOD-2) % MOD

이것을 알고 있다면 pow를 구현함으로써 해결 가능.

 

단 팩토리얼 구하는 과정에서 매번 MOD로 나눠주지 않으면 long long도 초과해버리니 주의 !

#include <iostream>
#include <vector>
#include<queue>
#include <string>
#include<stack>
#include<cmath>
#include <map>
#include<algorithm>
using namespace std;

long long MOD = 1000000007;


long long POW(long long b, long long m)
{
	if (m == 0)
	{
		return 1;
	}
	else if (m == 1)
	{
		return b;
	}

	if (m % 2)
	{
		return ( b *  ( POW(b, m - 1) % MOD)) % MOD;
	}
	else
	{
		long long midb = POW(b, m / 2) % MOD;
		return (midb * midb) % MOD;
	}
}
int main() {

	int N, K;
	cin >> N >> K;
	long long A = 1;
	long long B = 1;

	// N!
	for (int i = 1; i <= N; i++)
	{
		A *= i;
		A %= MOD;
	}
	
	// (N - K)!
	for (int i = 1; i <= N - K; i++)
	{
		B *= i;
		B %= MOD;
	}

	// (N - K)!K!
	for (int i = 1; i <= K; i++)
	{
		B *= i;
		B %= MOD;
	}


	cout << (A * POW(B, MOD - 2)) % MOD << endl;
}