[BOJ] 이항 계수 (Java)

[문제 개요]

nCr 이항 계수를 주어진 숫자로 나눈 나머지를 출력하시오.

각 문제마다 조건이 추가된다. 이 이항계수 시리즈는 수학적인 사고력을 높이고 특히 모듈러 연산에 대해 깊게 생각할 수 있게 해주는 문제들이다.

 

이항 계수 (1)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static long factorial(long n) {
        long result = 1;
        while(n > 1) {
            result = (result * n);
            n--;
        }
        return result;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        long N = Long.parseLong(st.nextToken());
        long R = Long.parseLong(st.nextToken());

        long first = factorial(N);
        long second = factorial(R) * factorial(N-R);

        System.out.println(first / second);
    }
}

 

이항 계수 (2)

이항 계수 (3)

+ 이항 계수 결과 값을 특정 숫자로 나누었을 때 나머지를 출력해야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private final static long P = 1000000007;
    private static long factorial(long n) {
        long result = 1;
        while(n > 1) {
            result = (result * n) % P;
            n--;
        }
        return result;
    }
    private static long pow(long base, long exponent) {
        long result = 1;
        while (exponent > 0) {
            if (exponent % 2 == 1) {
                result *= base;
                result %= P;
            }
            base = (base * base) % P;
            exponent /= 2;
        }
        return result;
    }
    /*
    * [*] nCr mod P = n! / r! (n-r)! mod P
    * = n! * (r! * (n-r)!)^-1 mod P ( ※ 나눗셈에 대한 mod 연산은 없으므로 곱하기 연산으로 바꾸어 준다. )
    * = ( n! mod P * (r! * (n-r)!)^-1 mod P ) mod P ( ※ 곱셈에 대한 mod 연산으로 바꾸어 준다. )
    *
    * [*] 페르마 정리 a^p mod p = a mod p 응용하여 a mod p 의 역원 구하기
    * = a^p-1 mod p = 1 mod p ( ※ 양 쪽에 a^-1 를 곱하였다. )
    * = a * a^p-2 mod p = 1 mod p 이므로 a mod p 의 역원은 a^p-2 mod p 이다.
    *
    * = ( n! mod P * (r! * (n-r)!)^p-2 mod P ) mod P ( ※ a mod p 의 역원으로 바꾸어 준다. )
    * */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        long N = Long.parseLong(st.nextToken());
        long R = Long.parseLong(st.nextToken());

        long first = factorial(N);
        long second = pow(factorial(R) * factorial(N-R) % P, P-2);

        System.out.println(first * second % P);
    }
}