이항계수 는
으로 정의되며 흔히 조합으로 알려져 있습니다.
n개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수를 이항계수라고 합니다.
우리는 이항계수가 가지는 이라는 성질을 이용하여 메모제이션 해주어 O(N^2)의 시간과 메모리 복잡도를 가지는 전처리 한번으로 매 쿼리를 O(1)에 처리해줄 수 있습니다.
하지만 BOJ)11401 이항 계수 3 처럼 N이 큰 쿼리가 들어올 경우 O(N^2)의 방법으로는 해결할 수 없습니다.
그래서 개선된 방법을 필요로 합니다.
이는 맨 위에 정의 된 를 이용하는 방법입니다.
문제 조건에서 모듈러를 위한 소수가 주어질텐데
을 소수
에 대한
의 역원을 구해주는 문제로 수정하여 해결하는 문제입니다.
우리는 동적 프로그래밍을 이용하여 n!을 계산하는데 O(N)의 시간 복잡도를 가지게 됩니다.
이제 소수 에 대한
의 역원을 구해주어야 하는데 이는 페르마의 소정리와 분할정복을 이용하여 O(log
)의 시간에 해결 가능합니다.
페르마의 소정리는 라는 수식인데 이를
로 변형하여
가
를 만족하는
가 되어 역원이
라고 정의됩니다.
그러므로 우리는 의
제곱에
을 곱해줌으로서 답을 구해줄 수 있습니다.
의
제곱은 분할 정복을 이용하여 O(log
)시간에 계산해 줄 수 있습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #define P 1000000007LL ll power(ll x, ll y) { //분할 정복을 이용하여 x^y 구하기 ll ret = 1; while (y > 0) { if (y % 2) { ret *= x; ret %= P; } x *= x; x %= P; y /= 2; } return ret; } | cs |
전체 시간 복잡도는 총 O(N*logP)가 되겠군요.
쿼리가 여러번 들어올 경우를 대비하여 n!을 O(N)의 시간에 전부 계산해 준 뒤 N개의 수에 대해서 n!의 inverse를 각각 O(log P) 시간에 전처리 해주면 총 O(N+NlogP)의 시간에 전처리가 가능하고 전처리 후에는 쿼리마다 O(1)의 시간에 처리가능 합니다.
자 여기서 더 개선이 가능할까요?
놀랍게도 O(N+logP)의 시간 복잡도에 이항계수 계산의 전처리가 가능합니다.
n * inverse(n!) = inverse((n-1)!) 라는 수식을 이용하여 (N!)의 inverse만 분할정복을 통하여 O(logP)의 시간에 한번 구해준다면 메모제이션을 통하여 n!의 inverse를 O(N) 시간에 처리 가능합니다.
따라서 O(N+logP)의 시간 복잡도에 이항계수 계산의 전처리가 가능합니다.
이어서 범위 내의 쿼리를 O(1)의 시간 복잡도에 처리해줄 수 있습니다.
다음은 BOJ)11401 이항 계수3 의 소스코드 입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <cstdio> #include <algorithm> #define P 1000000007LL typedef long long ll; using namespace std; ll fac[4000001], n, k, inv[4000001];//inv[x]의 정의는 x의inverse가 아닌 x!의 inverse ll power(ll x, ll y) { //분할 정복을 이용하여 x^y 구하기 ll ret = 1; while (y > 0) { if (y % 2) { ret *= x; ret %= P; } x *= x; x %= P; y /= 2; } return ret; } int main() { fac[1] = 1; for (int i = 1; i <= 4000000; i++) fac[i] = (fac[i - 1] * i) % P; //factorial 전처리 inv[4000000] = power(fac[4000000], P - 2); //페르마의 소정리를 이용하여 fac(400만)의 inverse를 구함(이때 분할 정복을 이용하여 logP의 시간에 처리) for (int i = 4000000 - 1; i >= 0; i--) inv[i] = (inv[i + 1] * (i + 1)) % P; //inverse(fac(i))=inverse(fac(i+1))*(i+1)이라는 수식을 이용하여 전처리 //총 O(N+logP)시간에 전처리를 끝냄 //전처리가 끝났기 때문에 어떤 쿼리가 들어와도 상수시간에 이항 계수를 계산 가능 scanf("%lld%lld", &n, &k); if (n == k || !k) { puts("1"); return 0; } ll r = (fac[n] * inv[n - k]) % P; r = (r*inv[k]) % P; printf("%lld\n", r); return 0; } | cs |
자 이제 이항계수를 활용한 여러 문제들을 풀어봅시다.
'알고리즘 관련 > 알고리즘&이론' 카테고리의 다른 글
제1종 스털링 수 (0) | 2017.05.29 |
---|---|
Minimum Path cover in DAG (0) | 2017.05.29 |
이항계수를 구하는 알고리즘 (9) | 2017.02.21 |
디닉 알고리즘(Dinic's Algorithm) (7) | 2017.02.13 |
이분 매칭(Bipartite Matching) (7) | 2017.02.12 |
Suffix Array & LCP Array(Longest Common Prefix Array) (4) | 2017.02.08 |
오호 아주 꿀팁이군요! 좋은 글 감사합니다.
감사합니다ㅎㅎ 맨날 방문하시는거 보니 제 팬이신거 같은데 시간날 때 사인 해드릴게요
ㅎㅎ 님 만날 시간에 여친 만나도록 할께요 ^^ 님도 여친만나세요 ㅎㅎ
오래 살기 싫으신가 보네여
분할정복으로 제곱하는 알고리즘을 이해하려고 해봤는데 이해가 안되는데 설명 가능하신가요?
예를들어 a의 8승을 구할때 그냥 계산한다면 8번의 연산이 필요합니다
하지만 a의 제곱의 제곱의 제곱을 구한다면 3번의 연산만에 해결할수있습니다
싸인해주세요
전 형 싸인 받을래요 ㅎㅎ
좋은 내용 감사합니다.
그런데, 예시 코드의 fac[1] = 1; 가 fac[0] = 1;로 변경되어야 맞을 것 같습니다.