effort0819   2년 전

N개 중 k개를 뽑는 경우의 수를 구하는 경우에 조합을 사용하려고합니다!


(combination(n-1,r-1)+ combination(n-1,r);

위와 같은 방법을 사용하면 n이 매우커질 경우 시간초과가 발생할 것 같네요. (2^n)

그래서

( combination(n-1, r-1) * n / r )  

위와 같은 방법을 사용하려고 하는데

문제에서 숫자가 너무 큰 것을 방지하여 %1000000 와 같은 나머지 연산을 계속해서 실행해야 하는데요 위 경우 r로 나누기 연산 때문에 소수가 발생하여 정확한 값을 구할 수 없는 것 같네요..

좋은 방법 있을까요?

effort0819   2년 전


@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까지이다보니.. 결국 오래걸리네요 ㅎㅎㅎ...

jseo   2년 전

p가 소수면 ap-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)를 구할수 있습니다.

effort0819   2년 전

@jseo


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

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

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

jseo   2년 전

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

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

댓글을 작성하려면 로그인해야 합니다.