b11401_이항계수3

b11401_이항계수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; } }

from http://elevensix.tistory.com/96 by ccl(A) rewrite - 2021-10-04 20:01:04