2749 피보나치 수 3 & 11401 이항 계수 3

안녕하세요..거의 3월이 끝나가는 시점에서 다시 글을 작성하네요. 허허

문제집 이름이 단기간 성장인데 부끄럽네요. :0

오늘은 피보나치 수 3 과 이항계수 3을 풀어봤습니다.

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

11401번: 이항 계수 3

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

2749번: 피보나치 수 3

 

[11401번: 이항 계수 3

자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

 

사실 수학적인 부분이 많이 들어가는 문제라서 풀까하다가

편-안

이렇게 성공으로 쭉 표시하고 싶어서 풀기로 했습니다.

-2749번 풀이-

우선 이 문제를 풀기전 공식을 하나 알고 있어야 합니다.

피사노주기 공식 : 피보나치 수를 어떤 수 K로 나눌 때, 나머지는 항상 주기를 가지게 되는데 이를 피사노 주기라고 합니다.

이때 주기의 길이가 P이면, N번쨰 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M으로 나눈 나머지와 같습니다. M이 10^k일 때, k>2라면, 주기는 항상 15 x 10^k-1입니다.

<출처 :https://www.acmicpc.net/blog/view/28>

문제에서 M은 10^6으로 이를 통해 주기의 길이 P는 15*10^5 임을 알수있습니다.

그렇다면 N번쨰 피보나치 수의 M으로 나눈 나머지는 = N을 P로 나눈 나머지를 M로 나눈 값과 같습니다.

import java.io.*;

class Main {
    static int mod = 1000000;
    static int p = 1500000;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        long x = Long.parseLong(bf.readLine());
        int answerNumber =(int)(x%p);
        long[] fibo = new long[answerNumber+1];
        fibo[0] = 0;
        fibo[1] = 1;

        for(int i=2; i<=answerNumber;i++){
            fibo[i] = (fibo[(i-1)]+fibo[(i-2)]) % mod;
        }
        System.out.println(fibo[answerNumber]);

    }
}

int 와 long의 범위를 헷갈려서 구현하는데 어려움이 있었습니다. 그래서 다른 게시물에 한번 정리를 할 계획인데..꼭 하겠습니다.

아무튼 저는 이 문제의 포인트는 저 포시,,아 피사노주기가 아닌 피보나치 수열을 DP로 구현하는데 초점을 두고 풀었습니다 .

-11401 이항 계수3

이 문제 또한 수학적인 지식이 필요합니다. 전 나름대로 수학을 좋아한다고 생각했는데 오늘보니 아니더군요.

이항계수를 구하는데 흔히 생각하는 방법은

이것 입니다. 

근데 그 범위가 4백만이니, O(n^2)으로 해결할 수 없습니다. 

 

그래서 이를 해결하기 위해서는 페르마의 소정리가 필요한데..

 

페르마의 소정리 : 소수 p와 정수 a에 대해서 a^p ≡ a ( mod p) 이고

                             만약 a와 p가 서로소 이면 a^p-1 ≡ 1(mod p)를 만족한다 ( ≡ 은 "~로  정의한다" 라는 의미래요) 

 

문제는 소수의 1,000,000,007로 nCr의 값을 나눈 나머지이니 ,  nCr = n! / (r! (n−r)!) mod p를 구하는 것으로 표현 가능 합니다. 

 

우선 분자인 n!의 mod p 를 구하는 것은 어렵지 않습니다. 하지만 분모가 문제인데, 이때 페르마의 소정리를 이용하면..

(r!(n - r)!) ^ p-2 의 mod p를 구하면 된다고 합니다. 설명이 참 부실해서 죄송합니다. 혹시 답답하시면 <출처 : https://rebro.kr/105> 여기로 가시면 아주 잘 정리해주셨습니다.

 

아무튼 아무튼! 이 문제의 주요 포인트는 (r!(n - r)!) ^ p-2을 구하는 것입니다. a^k의 거듭제곱은 분할정복을 통해 구하면 O(log k)로 구할 수 있습니다.

import java.io.*;
import java.io.IOException;

class Main {
    static long p = 1_000_000_007;
    public static long factorial(long n){
        long answer = 1L;
        while(n>1){
            answer *= n;
            answer %=p;
            n--;
        }
        return answer;
    }
    public static long powLoop(long n,long k){
        long answer =1;
        while(k>0){
            if(k%2==1){
                answer *=n;
                answer %=p;
            }
            n = (n*n)%p;
            k = k/2;
        }
        return answer;
    }
    public static long powRecursion(long n, long k){
        if(k==1){return n%p;}

        long tmp = powRecursion(n,k/2);

        if(k%2==1){
            return (tmp*tmp%p)*n%p;
        }
        return tmp*tmp%p;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] inputValue = bf.readLine().split(" ");
        int n = Integer.parseInt(inputValue[0]);
        int k = Integer.parseInt(inputValue[1]);
        long son = factorial(n);
        long mother = factorial(k)*factorial(n-k)%p;
        System.out.println(son*powRecursion(mother,p-2)%p);
    }
}

 

후기

1. dp는 역시 점화식..?

2. 분할정복은 중요하다!

3. 나는 수학을 안좋아하는 걸로.