백준 11401 - 이항 계수 3 (분할정복, JAVA)

참조 목록

https://www.acmicpc.net/blog/view/29

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=dmbs335&logNo=221074084832

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

 

 

 

 

개념이 어렵다

 

근데 그 개념을 이해하면 구현은 꽤 쉬움

 

일단 이거 풀려면 제곱을 분할정복으로 처리하는 방법을 알아야함

 

근데 이 문제 풀 때 쯤이면 그 정도는 당연히 풀고 왔을거라 생각함, 따로 그거에 대해서는 글을 쓰진 않겠다.

 

아무튼 

https://kimximya.tistory.com/7

페르마의 소정리

 

https://kimximya.tistory.com/9

모듈러 곱셈의 역원

 

이거 두개를 읽어서 개념을 숙지했다 치자

 

방법론

 

 

 

1. 대충 N값 K값 입력 받자, 이는 nCk 를 의미하고, 그리고 1000000007는 p로 상수처리 하자

2. 좀더 효율적인 처리 위해서 K값이 N/2 값을 넘기면 K = N-K 로 바꿔주자, 이거 그냥 nCr 기초원리임

 

3. 팩토리얼 계산해주는 함수인 fac 함수를 만드는데, 입력값으로 시작값과 끝나는 값을 입력받음

일반 팩토리얼 n! 은 n이랑 1 집어넣으면 되고, n * (n-1) * ... * (n - r + 1) 을 계산하려면 n이랑

n - r + 1 집어 넣으면 됨, 그리고 이 함수는 그냥 포문 돌리면서 곱해주는건데,계속 p로 모듈러 연산 해주면 된다. 이거에 관한 모듈러 연산 개념은 기본 개념이라 여기다 적진 않는다.

 

4. 거듭제곱을 분할정복으로 처리해주는 함수인 expo를 제작한다. 이거도 기본적으로 숙지해야 하는 사항이라 디테일하게 다루지는 않는다.

 

5. n * (n-1) * ... * (n - r + 1)값을 구하자, 이를 A라 한다.

6. k! 값을 구하자, 이를 B라 한다.

7. k!을 페르마의 소정리, 모듈러 곱셈의 역원에 의해서 (k!) ^ (p-2) 값을 구한다. 이를 C라 하자

8. 최종적으로 (A*C) % p 를 구한다.

 

핵심요약

 

 

import java.io.*;
import java.util.*;

public class Main
{
	static final long p = 1000000007;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		st = new StringTokenizer(input.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		if ( K > N/2 )
			K = N-K;
		
		long A = fac(N, N-K+1);
		long B = fac(K, 1);
		long C = expo(B, p-2);
		long D = (A * C) % p;
		
		
		output.write( D + "" );
		output.close();
	}
	
	public static long fac (int a, int b)
	{
		if (a == 0)
			return 1;
		
		long result = 1;
		
		for (long i=a; i>=b; i--)
			result = ( result * i ) % p;
		
		return result;
	}
	
	public static long expo (long a, long r)
	{
		if (r == 0)
			return 1;
		
		if (r == 1)
			return a;
		
		if (r % 2 == 0)
		{
			long h = expo(a, r/2) % p;
			return ( h * h ) % p;
		}
		else
			return  ( a * expo(a, r-1) ) % p;
	}
}