SWEA[5607] - 조합[D3]

링크

SWEA[5607]

문제설명

• 큰 수 nCr%prime

문제풀이

• 페르마 소정리
• 최적화
  • 분할 정복
  • 메모이제이션

문제코드

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution5607 {

    public static long prime = 1234567891;
    public static long[] fac = new long[1000001];

    public static long pow(long a, long b) {
        if(b==0) {
            return 1;
        }
        else {
            long temp = pow(a,b/2);
            if(b%2==0) return (temp*temp)%prime;
            else return ((temp*temp)%prime*a)%prime;
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("res/swea/5607.txt"));
        Scanner sc = new Scanner(System.in);
        fac[0]=1;
        for (int i = 1; i <= 1000000; i++) {
            fac[i] = (fac[i-1]*i)%prime;
        }

        int T = sc.nextInt();
        for (int test_case = 1; test_case <= T; test_case++) {
            long up=1;
            long down=1;
            int N = sc.nextInt();
            int R = sc.nextInt();
            up = fac[N];
            up = up*pow(fac[N-R],prime-2)%prime;
            up = up*pow(fac[R],prime-2)%prime;

            System.out.println("#"+test_case+" "+up);
        }
    }
}

아쉬운점

• 페르마 소정리 이해 제대로 못했었음
  • 분모, 분자 각각 따로 모듈러를 취하면 값이 다르게 나옴
    • (2*2*3*3)mod5/(2*2)mod5 = 1/4 =/= (2*2*3*3/2*2)mod5 = 4
  • 분모를 분자로 바꿔주는게 페르마 소정리
    • {(2*2*3*3)/(2*2)}mod5 = {(2*2*3*3)*2^(5-2)*2^(5-2)}mod5 = 4
• pow함수 분할정복 작성할 때, 함수 호출도 한번씩만 하게 해야함
  • 함수호출을 계속했었음

잘한점

• 페르마 소정리 공부