b11401_이항계수3

11401번: 이항 계수 3

이 문제의 범위는 1<=N<=4000000, 0<=K<=N 로 매우 큰 수가 나올 수 있기 때문에 nCr 도 매우 큰 수의 형태로 구해야한다. 그래서 모듈러분배법칙을 이용해야하는데 nCk를 구하는 공식은 분수형태이므로 페르마의 소정리를 한 후 적용해야한다. 이러한 문제는 SWEA의 6026번 성수의 비밀번호 공격과 같은 형태의 문제라고 볼 수 있다.

성수의 비밀번호 공격 문제처럼 페르마의 소정리를 한 후에는 매우 큰 제곱근을 구해야하기 때문에 빠른 제곱 구하기를 통해 제곱근을 반으로 나누고 모듈러를 사용해준다. 마지막으로 정리된 식을 팩토리얼을 통해 구하면 된다. 팩토리얼을 구할 때도 마찬가지로 모듈러를 사용하여 수를 줄여줘야한다.

package com.pascal_triangle.b11401_이항계수3;

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

// 단순 조합 공식을 모듈러의 분배법칙, 페르마의 소정리로 이용
// 조합 공식 : nCk = n! / (r! * (n-r)!)
// 모듈러의 분배법칙 적용하기 위해 페르마의 소정리 적용 : [n! * {r!*(n-r)!}^(MOD-2)] % MOD

public class Main {
    static long n;
    static long MOD = 1_000_000_007;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());   // 1<=N<=4000000
        long K = Integer.parseInt(st.nextToken());   // 0<=K<=N

        //nCr = (n-1 C k-1) + (n-1 C k)

        System.out.println(nCk(K));

        br.close();

    }


    // nCk = n! / (r! * (n-r)!)
    // = [ n! * { r!*(n-r)! }^(MOD-2) ] %MOD
    private static long nCk(long r) {
        if(n==r || r==0) return 1;

        long result = 0;
        //result = fac(n) / (fac(r) * fac(n-r));
        //= (fac(n) * ((fac(r) * fac(n-r)))^(MOD-2)) % MOD
        //= (fac(n) * ( (fac(r)^(MOD-2) * fac(n-r)^(MOD-2) ) % MOD
        long l1 = fac(n);
        long l2 = pow(fac(r),MOD-2);
        long l3 = pow(fac(n-r),MOD-2);

        result = ((l1*l2)%MOD *l3)%MOD;
        return result;
    }

    private static long pow(long a, long b) {
        if(b==1) return a;

        long half = pow(a,b/2); // 빠른제곱구하기
        if(b%2==0){
            return (half*half) %MOD;
        }else{
            return ((half*half)%MOD * (a%MOD) )%MOD;
        }
    }

    public static long fac(long x) {
        long fac = 1L;

        while(x > 1) {
            fac = (fac * x) % MOD;
            x--;
        }
        return fac;
    }

}