백준 11401번 : 이항계수 [C#]

이항계수란 무엇인가

이렇다고 합니다.

 

개념은 한 번 읽어보고, 공식을 보면 팩토리얼을 사용하네요.

 

N이 400만인데, 400만의 팩토리얼을 구한다는건 숫자가 너무 커지고, 중간에 어떤 연산을 거쳐서 숫자의 크기를 어느정도 유지해가며 N!을 구해야겠습니다.

 

1000000007으로 나누는 과정에서의 나머지는 나머지 연산 분배법칙을 활용할 수 있을 것 같습니다.

 

(mod m) = m으로 나눈 나머지라는 뜻. 

 

추가로 페르마의 소정리까지 알아야 이 문제를 해결할 수 있습니다.

 

a가 정수, p가 소수일 때 이 공식이 성립하는데, 여기서 a= N이든 R이 될 수 있고, P는 1000000007입니다.

 

a와 1이 서로소이기 때문에 양 변을 a로 나누면 

 

 

위에서 배운 내용을 어떻게 적용하냐면

 

1.  이 공식으로  분모에 있는 k! * (n-k)! 을 페르마의 소정리를 활용해 지수의 형태로 변형하여

분자* (분모의 변형) (mod p)

모양을 만듭니다.

 

2. 곱셈의 나머지 연산 형태가 되었으니까 나머지 연산의 곱셈 분배법칙을 사용합니다.

> ( 분자 (mod p) * (분모의 변형) (mod p) ) (mod p)

 

3. 거듭제곱 형태인 분모의 변형도 곱셈의 나머지 연산 형태이므로 숫자가 커지지 않게 유지하며 계산합니다.

 

4. 식에 사용할 팩토리얼, 지수 연산을 함수로 만들고 계산합니다.

 

using System;

class Program
{
    static long P = 1000000007;

    static void Main()
    {
        string[] input = Console.ReadLine().Split();
        long n = long.Parse(input[0]);
        long k = long.Parse(input[1]);

        if (k == 0 || n == k)
        {
            Console.WriteLine(1);
            return;
        }

        // 1. 분자: n! 구하기
        long numerator = Factorial(n);

        // 2. 분모: (k! * (n-k)!) 구하기
        long denominator = (Factorial(k) * Factorial(n - k)) % P;

        // 3. 최종 계산: 분자 * (분모^(P-2)) % P
        // 페르마의 소정리에 의해 분모로 나누는 것은 분모의 P-2승을 곱하는 것과 같음
        long result = (numerator * Power(denominator, P - 2)) % P;

        Console.WriteLine(result);
    }

    // O(N)으로 팩토리얼 계산
    static long Factorial(long n)
    {
        long res = 1;
        for (long i = 2; i <= n; i++)
        {
            res = (res * i) % P;
        }
        return res;
    }

    // O(log P)로 거듭제곱 계산 (분할 정복)
    static long Power(long a, long b)
    {
        long res = 1;
        a %= P;
        while (b > 0)
        {
            // 지수가 홀수면 base를 한번 곱해줌
            if (b % 2 == 1) res = (res * a) % P;
            
            // base를 제곱하고 지수를 절반으로 줄임
            a = (a * a) % P;
            b /= 2;
        }
        return res;
    }
}