@rms

nCk 인경우에

    for(int i=0; i<=n; i++){

        for(int j=0; j<=min(i,k); j++){

            if(j==0 || j==i){

                memo[i][j] = 1;

            }

            else{

                memo[i][j] = (memo[i-1][j-1] + memo[i-1][j])%1003001;

            }

        }

    }

이처럼 dp를 이용해봣는데 n의 범위가 1000000까지이다보니.. 결국 오래걸리네요 ㅎㅎㅎ...

p가 소수면 a^p-2 = a^-1 (mod p) 가 성립합니다.

p = 1003001이 소수이기 때문에 

n! * [(n - k)!k!]^-1 = n! * [(n - k)!k!]^p-2 (mod p)

팩토리얼 구하는데 O(n), 거듭제곱 구하는데 O(log p), 총 시간 복잡도 O(n + log p)로 C(n, k)를 구할수 있습니다.

@jseo

p가 소수면 a^p-2 = a^-1 (mod p) 가 성립합니다.

이 부분이 이해가 가지 않네요!

a = 3, p = 5 라면.. 3^3 = (3^-1)%5 인데... 틀리지 않나요?

이거 읽어보시는것도 좋을것 같네요

https://www.acmicpc.net/blog/v...