[BOJ] 11401번 이항 계수 3

문제

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

입력

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

출력

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

예제

// 입력
5 2

// 출력
10

코드

• C++17

#include <iostream>

using namespace std;

using LL = long long;

constexpr LL M = 1'000'000'007;

LL N, K;
LL kFact, invOfkFact, numer;

inline LL power(LL x, LL y)
{
	LL toRet = 1;
	while (y > 0)
	{
		if (y & 1)
			toRet = toRet * x % M;
		x = x * x % M;
		y >>= 1;
	}
	return toRet;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> K;

	kFact = numer = 1;
	if (K > (N >> 1))
		K = N - K;

	// numer의 값은 N! / (N - K)! 이다.
	for (int i = 0; i < K; ++i)
	{
		numer = numer * (N - i) % M;
		kFact = kFact * (K - i) % M;
	}

	// K!의 역원을 구하기 위해 페르마의 소정리를 이용한다.
	// 페르마의 소정리는 https://ko.wikipedia.org/wiki/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98_%EC%86%8C%EC%A0%95%EB%A6%AC 을 참고한다.
	invOfkFact = power(kFact, M - 2);

	cout << numer * invOfkFact % M;
}

• C# 6.0

using System;

namespace AlgorithmsByCsharp
{
    class Program
    {
        const long M = 1000000007L;
        static long N, K;
        static long kFact, invOfkFact, numer;
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split();
            N = long.Parse(inputs[0]);
            K = long.Parse(inputs[1]);
            if (K > (N >> 1))
                K = N - K;

            numer = kFact = 1;
            for (int i = 0; i < K; ++i)
            {
                numer = numer * (N - i) % M;
                kFact = kFact * (K - i) % M;
            }
            invOfkFact = Power(kFact, M - 2);

            Console.Write(numer * invOfkFact % M);
        }

        static long Power(long b, long exp)
        {
            long toRet = 1L;
            for (long i = exp; i > 0; i >>= 1)
            {
                if (isOdd(i))
                {
                    toRet = toRet * b % M;
                }
                b = b * b % M;
            }
            return toRet;
        }

        static bool isOdd(long n) => (n & 1) == 1;
    }
}

• Python

import sys
input = sys.stdin.readline
print = sys.stdout.write

M = 1000000007
def power(b, exp):
    toRet = 1
    while exp > 0:
        if exp & 1:
            toRet = toRet * b % M
        b = b * b % M
        exp >>= 1
    return toRet

inputs = input().split()
N = int(inputs[0])
K = int(inputs[1])
if K > (N >> 1):
    K = N - K

kFact = numer = 1
for i in range(K):
    numer = numer * (N - i) % M
    kFact = kFact * (K - i) % M
inv = power(kFact, M - 2)

print(str(numer * inv % M))