[Java] 백준 11401번 이항 계수 3

이항계수 문제입니다.

nCr로 입력받으며 이는 아래 코드로 구할 수 있습니다.

for (int i = 0; i < r; ++i) {
    a *= (n - i);
    b *= (r - i);
}

위의 코드에서 모듈러 연산을 추가해주어야 합니다.

그리고 구해진 값에서 a/b를 해야하는데
나눗셈을 하게 될 경우 모듈러 연산의 결과가 틀려지게 됩니다.

그래서 페르마 소정리를 통해서 계산해주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        long ans = 0;
        int mod = 1000000007;

        long a = 1;
        long b = 1;
        for (int i = 0; i < r; ++i) {
            a *= (n - i);
            b *= (r - i);
            a %= mod;
            b %= mod;
        }

        long b2 = 1;
        int exp = mod - 2;
        while(exp > 0) {
            if(exp % 2 > 0) {
                b2 *= b;
                b2 %= mod;
            }

            b*=b;
            b %= mod;
            exp /=2;
        }
        ans = a * b2;
        ans %= mod;

        bw.write(ans + "\n");
        bw.close();
    }
}