미리 계산한 팩토리얼로 nCr 구하기

많은 문제에서 n개 중 r개를 선택하는 방법의 수를 묻고, 이를 nCr로 씁니다. 대회에서는 이 개수를 소수 모듈러 아래에서 구하게 합니다. 🧮

기본 공식은 nCr이 n 팩토리얼을 r 팩토리얼과 n-r 팩토리얼의 곱으로 나눈 값이라는 것입니다. 문제는 모듈러에서의 나눗셈입니다.

하나의 팩토리얼도 천문학적으로 커지므로 각각을 p로 모듈러 연산해야 합니다. 그러면 모든 값이 작게 유지되면서도 공식은 모듈러 아래에서 정확하게 성립합니다.

필요한 가장 큰 n까지 fact 배열을 한 번만 만드세요. 각 원소는 이전 원소에 인덱스를 곱한 뒤, 계산하는 동안 p로 모듈러 연산한 값입니다.

공식에서 두 개의 팩토리얼로 나누므로 해당 팩토리얼의 모듈러 역원이 필요합니다. 역원을 사용하면 나눗셈을 깔끔한 곱셈으로 바꿀 수 있다는 점을 기억하세요.

p-2를 지수로 하는 pow를 사용해 페르마의 방법으로 가장 큰 팩토리얼의 역원을 한 번만 계산하세요. 그 한 번의 호출이 나머지 계산의 시작점이 됩니다.

나머지 역팩토리얼은 한 번의 역방향 순회로 구하세요. 각 값은 다음 값에 인덱스를 곱해 계산합니다. 추가적인 pow 호출은 필요하지 않습니다.

이제 nCr은 fact[n]과 inv_fact[r], inv_fact[n-r]을 곱한 뒤 모두 p로 모듈러 연산한 값입니다. 질의 하나마다 배열 조회 세 번과 곱셈 두 번이면 됩니다.

미리 계산을 마치면 모든 조합의 답을 O(1) 시간에 구할 수 있습니다. 문제에서 수천 개의 nCr 값을 요구할 때 이 방식이 특히 강력한 이유입니다.

r이 음수이거나 n보다 크면 답은 0입니다. 팩토리얼 배열의 범위를 벗어나지 않도록 먼저 이 범위를 확인하세요.

배열 크기를 모든 질의의 최대 n에 약간의 여유를 더한 값으로 설정하세요. 너무 작은 한도는 여기서 인덱스 오류가 발생하는 흔한 원인입니다.

미리 계산한 뒤 nCr 질의 하나를 처리하는 데 얼마나 걸리나요?

이제 팩토리얼과 역원을 한 번만 미리 계산한 뒤, 배열 조회 세 번으로 각 nCr을 O(1)에 구할 수 있습니다. r의 범위를 확인하고 배열 크기도 충분히 크게 잡으세요. 🏆