6026_성수의비밀번호공격

SW Expert Academy

문제 풀이

경우의 수 식 구하기

지문 개수 : 사용되는 문자 종류의 수인 M, 비밀번호의 수 : N

찍힌 지문은 비밀번호에 전부 사용해야한다.
그렇기 때문에 중복순열 M^N (M가지수를 N개 뽑는 경우의 수)에서 전부 다 사용 하지 않는 경우는 빼줘야한다.

예를 들어 M=3, N=4일 때

찍힌 지문을 전부 사용하는 경우 (3^4)에서 두가지를 사용하는 경우를 먼저 뺀다고 생각했을 때 3C2 * 2^4인데 이 식은 한가지만 사용하는 경우도 포함 되어 있다.

다시 말하자면  전부 사용하는 경우 (3^4)에서 2가지만 사용하는 경우 (3C2 * 2^4)를 빼는데,,, 이렇게 2가지만 사용하는 경우를 빼는 부분에 하나만 사용하는 경우가 각각 두번씩 포함되어 있음.. 때문에 한 가지인 경우를 다시 더해줘야 한다.
+ 2C1 * 1^4

이렇게 빼 줬던 부분을 다시 더해주는 것을 "전사함수의 포함/배제의 원리"라고 한다.

다시 정리하여 식을 정리하자면 M=3, N=4일 때의 해는 (3^4) - (3C2 * 2^4) + (2C1 * 1^4) 이라고 할 수 있다.

위의 규칙을 통해 얻은 식

이 계산식을 보면 빼고 더하고 빼고 더하고,, 이러한 규칙이 반복되기 때문에 Σ (-1)^i * kCi * (k-i)^n 식으로 표현할 수 있다.

Σ (-1)^i * kCi * (k-i)^n

큰 수의 nCr 구하기

문제에서 수는 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력 하라고 하였다. 하지만 nCr의 식은 분수형태이고, 분수형태는 "모듈러 분배법칙" 사용 못한다. 그래서 분모를 분자로 올려주는 역할인 "페르마의 소정리"를 사용한다.

"페르마의 소정리(Fermat's little Theorem)"란?

한 마디로 임의의 소수 p와 서로소인 한 수의 (p−1)승을 p로 나눈 나머지는 무조건 1이라는 정리. 출처 : 나무위키

 64^70을 71로 나눈 나머지는 11이라는 것을 순식간에 알 수 있다. 더 나아가서, 64^6470000000을 71로 나누면 나머지가 1이라는 엄청난 결론을 낼 수 있다.

(1/x)% MOD 하고 싶다면 페르마의 소정리에 의해 x^(MOD-2)

 

위의 이론을 바탕으로 nCr을 모듈러의 분배법칙을 이용하기 위해 페르마의 소정리를 적용하면 다음과 같다.
nCr
= [ n! / { (n-r)! * r! } ] % MOD
= [ n! * { (n-r)! * r! }^(MOD-2) ] % MOD

[ n! * { (n-r)! * r! }^(MOD-2) ] % MOD

 

반복되는 Factorial 를 전처리하기

위의 nCr의 식에서 factorial이 난무한 걸 볼 수 있다. 이런 팩토리얼을 줄이기 위해 재사용 가능한 코드를 만들어보자

    /// 매번 동일한 값이기 때문에 한번만 구해놓고 재사용하자
    static void pre(){ // factorial 초기화 하는 함수.. 1<= N,M <=100
        fac = new long[101];
        fac[0] = fac[1] = 1;
        for (int i = 2; i < fac.length ; i++) {
            fac[i] = (fac[i-1] * i) % MOD;    // 여기서도 값이 매우 크게 나온다.. 어차피 곱할것이기 때문에 모듈러 사용
        }
   }

 

빠른 제곱 구하기

((n-r)! * r!)^(MOD-2)의 식에서 매우 큰 제곱근을 해야하기 때문에 범위를 초과한다. 빠른 제곱 구하기로 제곱을 분할하여 사용해 보자

    // a^b
    private static long pow(long a, int 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; // half * half * a : 곱하는 도중에 또 커질 수 있으니까 .. 모듈러의 분배법칙..
        }
    }

 

nCr 구하기

위에서 했던 작업들을 통해 nCr을 구하는 코드를 작성해보자

nCr 
= n!/ ((n-r)! * r!) 
= ( n! * ((n-r)! * r!)^(MOD-2) ) % MOD // 모듈러의 분배법칙을 이용하기위해 페르마의 소정리
=  n! * ((n-r)!)^(MOD-2) * (r!)^(MOD-2) // 제곱 분배

    // nCr = n!/ ((n-r)! * r!)
    // n!는 너무 크기 때문에 바로 계산 X .. "모듈러 분배법칙" 이용해야함.. 하지만 nCr의 식은 분수형태..
    // 분수형태는 모듈러 분배법칙 사용 못한다. 그래서 "페르마의 소정리"를 사용한다.
    // 페르마의 소정리 --> 분모를 분자로 올려주는 역할

    // nCr
    // = n!/ ((n-r)! * r!)
    // = ( n! * ((n-r)! * r!)^(MOD-2) ) % MOD   // 모듈러의 분배법칙을 이용하기위해 페르마의 소정리
    // = n! * ((n-r)!)^(MOD-2) * (r!)^(MOD-2)   // 제곱 분배
   private static long nCr(int r) {
        if(r==0) return 1;
        
        long l1 = fac[M];      // 중복되는 factorial를 전처리를 통해 재사용하자
        long l2 = pow(fac[M-r],MOD-2);   //(MOD-2)의 제곱은 매우매우 크다.. 때문에 "빠른 제곱 구하기"를 사용한다. 분할하여 제곱하는 방법
        long l3 = pow(fac[r],MOD-2);

        //  n! * ((n-r)!)^(MOD-2) * (r!)^(MOD-2) = l1 * l2 * l3
        return ((l1 * l2)%MOD * l3)%MOD;  // 또 l1*l2곱하는 중에 범위를 초과할수 있으므로 모듈러연산법칙
    }

 

경우의 수 구하기

위의 코드를 바탕으로 Σ (-1)^i * kCi * (k-i)^n 을 구해보자

    // 함수의 개수 : Σ (-1)^i * kCi * (k-i)^n
    // --> 함수의 개수 : Σ l1 * l2 * l3
    private static long solve() {
       long total = 0;
        for (int i = 0; i <= M; i++) {
            long l1 = i%2 == 0 ? 1 : -1; //(-1)^i : 홀짝으로 음,양이 나뉘어짐
            long l2 = nCr(i);
            long l3 = pow(M-i,N);
            long result = ((l1 * l2)%MOD * l3)%MOD; // 또 모듈러연산분배법칙
            // 이제 시그마,, 더해주는 작업중에 result가 음수가 되어 문제가 생길 수 있다.. 어차피 모듈러하기때문에 MOD를 더해준다..그러면 절대로 음수가 나올 수 없다
            total = (total + result + MOD)%MOD;
        }
        return  total;
    }

 

완성 코드

package w0928.SWEA6026_성수의비밀번호공격;

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

//동생의 비밀번호로 가능한 것의 개수는??
public class Solution {

    static int N,M;
    static int MOD = 1_000_000_007; // , 대신에 _ 쓸 수 있다
    static long [] fac;

	// factorial 초기화 하는 함수.. 1<= N,M <=100
    // 매번 동일한 값이기 때문에 한번만 구해놓고 재사용하자
    static void pre(){ 
        fac = new long[101];
        fac[0] = fac[1] = 1;
        for (int i = 2; i < fac.length ; i++) {
            fac[i] = (fac[i-1] * i) % MOD;  
        }
   }

   public static void main(String[] args) throws IOException {
        pre();  // factorial 초기화 함수
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());   // 지문 수 (사용되는 문자 종류)
            N = Integer.parseInt(st.nextToken());   // 비번 자리수

            long result = solve();

            System.out.println("#"+t+" "+result);
        }

        br.close();
    }

    // 함수의 개수 : Σ (-1)^i * kCi * (k-i)^n 
    // --> 함수의 개수 : Σ l1 * l2 * l3
    private static long solve() {
       long total = 0;
        for (int i = 0; i <= M; i++) {
            long l1 = i%2 == 0 ? 1 : -1; 
            long l2 = nCr(i);
            long l3 = pow(M-i,N);
            long result = ((l1 * l2)%MOD * l3)%MOD; 
         
            total = (total + result + MOD)%MOD;
        }
        return  total;
    }

    // nCr
    // = n!/ ((n-r)! * r!)
    // = ( n! * ((n-r)! * r!)^(MOD-2) ) % MOD   // 모듈러의 분배법칙을 이용하기위해 페르마의 소정리
    // = n! * ((n-r)!)^(MOD-2) * (r!)^(MOD-2)   // 제곱 분배
   private static long nCr(int r) {
        if(r==0) return 1;
        
        long l1 = fac[M];      
        long l2 = pow(fac[M-r],MOD-2);  
        long l3 = pow(fac[r],MOD-2);

        //  n! * ((n-r)!)^(MOD-2) * (r!)^(MOD-2) = l1 * l2 * l3
        return ((l1 * l2)%MOD * l3)%MOD; 
    }

    // a^b
    private static long pow(long a, int 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; 
        }
    }
}

 

주석 있는 버전

package w0928.SWEA6026_성수의비밀번호공격;

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

//동생의 비밀번호로 가능한 것의 개수는??
public class Solution {

    static int N,M;
    static int MOD = 1_000_000_007; // , 대신에 _ 쓸 수 있다
    static long [] fac;

    // factorial 초기화 하는 함수.. 1<= N,M <=100
    /// 매번 동일한 값이기 때문에 한번만 구해놓고 재사용하자
    static void pre(){
        fac = new long[101];
        fac[0] = fac[1] = 1;
        for (int i = 2; i < fac.length ; i++) {
            fac[i] = (fac[i-1] * i) % MOD;    // 여기서도 값이 매우 크게 나온다.. 어차피 곱할것이기 때문에 모듈러 사용
        }
   }

   public static void main(String[] args) throws IOException {
        pre();  // factorial 초기화 함수
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());   // 지문 수 (사용되는 문자 종류)
            N = Integer.parseInt(st.nextToken());   // 비번 자리수

            long result = solve();

            //비밀번호 개수(경우의 수)를 1,000,000,007로 나눈 나머지를 출력
            System.out.println("#"+t+" "+result);
        }

        br.close();
    }

    //찍힌 지문은 비밀번호에 전부 사용해야한다.
    // 그렇기때문에 중복순열(M^N:M가지수를 N개 뽑는 경우의 수)에서 전부다사용하지 않는경우를 빼줘야한다.
    // 예를 들어 M=3, N=4일 때..
    // 전부사용하는 경우 (3^4)
    // - 2가지만 사용하는 경우 (3C2 * 2^4) -> 하나만 사용하는 경우가 두번씩 포함되어 있음.. 때문에 한가지인 경우를 다시 더해줘야 한다.
    // + 2C1 * 1^4 // 이를 "전사함수의 포함/배제의 원리"라고 한다
    // 빼고 더하고 빼고 더하고,, 이러한 규칙이 반복되기 때문에 Σ(-1)^i*kCi*(k-i)^n 공식으로 표현할 수 있다.

    // 함수의 개수 : Σ (-1)^i * kCi * (k-i)^n
    // --> 함수의 개수 : Σ l1 * l2 * l3
    private static long solve() {
       long total = 0;
        for (int i = 0; i <= M; i++) {
            long l1 = i%2 == 0 ? 1 : -1; //(-1)^i : 홀짝으로 음,양이 나뉘어짐
            long l2 = nCr(i);
            long l3 = pow(M-i,N);
            long result = ((l1 * l2)%MOD * l3)%MOD; // 또 모듈러연산분배법칙
            // 이제 시그마,, 더해주는 작업중에 result가 음수가 되어 문제가 생길 수 있다.. 어차피 모듈러하기때문에 MOD를 더해준다..그러면 절대로 음수가 나올 수 없다
            total = (total + result + MOD)%MOD;
        }
        return  total;
    }

    // nCr = n!/ ((n-r)! * r!)
    // n!는 너무 크기 때문에 바로 계산 X .. "모듈러 분배법칙" 이용해야함.. 하지만 nCr의 식은 분수형태..
    // 분수형태는 모듈러 분배법칙 사용 못한다. 그래서 "페르마의 소정리"를 사용한다.
    // 페르마의 소정리 --> 분모를 분자로 올려주는 역할

    // nCr
    // = n!/ ((n-r)! * r!)
    // = ( n! * ((n-r)! * r!)^(MOD-2) ) % MOD   // 모듈러의 분배법칙을 이용하기위해 페르마의 소정리
    // = n! * ((n-r)!)^(MOD-2) * (r!)^(MOD-2)   // 제곱 분배
   private static long nCr(int r) {
        if(r==0) return 1;

        long l1 = fac[M];      // 중복되는 factorial를 전처리를 통해 재사용하자
        long l2 = pow(fac[M-r],MOD-2);   //(MOD-2)의 제곱은 매우매우 크다.. 때문에 "빠른 제곱 구하기"를 사용한다. 분할하여 제곱하는 방법
        long l3 = pow(fac[r],MOD-2);

        //  n! * ((n-r)!)^(MOD-2) * (r!)^(MOD-2) = l1 * l2 * l3
        return ((l1 * l2)%MOD * l3)%MOD;  // 또 l1*l2곱하는 중에 범위를 초과할수 있으므로 모듈러연산법칙
    }

    // a^b
    private static long pow(long a, int 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; // half * half * a : 곱하는 도중에 또 커질 수 있으니까 .. 모듈러의 분배법칙..
        }
    }
}