[BaekJoon/백준] 11401번 분할정복 (때려칠뻔)

분할정복 카테고리긴 한데, 그냥 수학문제다.

 

진짜 이거풀다가 성격 더 버렸다.

수학적인게 계속 나오니까 뭔소린지 모르겠어서 진짜 백준 처음으로 문제 포기하고싶었다.

차라리 빡센 알고리즘 문제들이 훨씬 낫다.. 진짜 뭔소린지 아예 가늠이 안되고 이해도 안되니 너무짜증남.

 

설명은 두 블로그를 참고했다.

m.blog.naver.com/hongjg3229/221650178981

okayoki2484.tistory.com/129

두 블로그중 특히 아래 블로그가 나같은 수포자에게 도움을 주었다.

#include <stdio.h>

int N, K;
long long m[4000001] = {1, };

long long pow_(long long a, long long b) {
    
    if(b == 1)
        return a;
    
    long long result = pow_(a, b / 2) % 1000000007;
    result = (result * result) % 1000000007;
    
    if(b % 2)
        result = (result * a) % 1000000007;
    
    return result;
    
}

int main() {
    
    scanf("%d %d", &N, &K);
    
    for(int i = 1; i <= N; i++) {
        m[i] = (i * m[i - 1]) % 1000000007;
    }
    
    
    printf("%lld", (m[N] *pow_((m[N-K]*m[K])%1000000007 , 1000000005))%1000000007);
}

코딩도 뭐 어떻게한지도 모르겠다. 진짜 개짜증나고 시간만 너무썼다.

 

 

[알아둘 것]

곱셈 단위의 (A * B) % P 에는 분배법칙이 가능하나

분수로 존재하는 나눗셈 단위 (A / B) % P 에서는 P 분배를 해줄 수 없다.

 

+ (A * B) % P = (A % P) * (B % P) % P 

 

 

문제 꼴도보기싫다.

하.. 진짜 모듈러니 페르마의 소정리니 뭐니ㅡㅡ