Funcia
Lv.3combinatoricsmathmodular-inverse

조합의 수 질의

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

각 질의 queries[i] = [n, r]에 대해 서로 다른 n개 중 r개를 고르는 방법의 수 (nr)\binom{n}{r}를 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지를 구해, 질의 순서대로 배열에 담아 반환하세요.

입출력 예

queriesresult
[[5, 2], [10, 0], [10, 10], [6, 3]][10, 1, 1, 20]
[[1000000, 500000]][996692777]

입출력 예 설명

예 1 — (52)=10\binom{5}{2} = 10, (100)=(1010)=1\binom{10}{0} = \binom{10}{10} = 1, (63)=20\binom{6}{3} = 20입니다.

예 2 — 실제 값은 30만 자리가 넘는 수지만 나머지만 구하면 됩니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(queries: int[][]) → int[]

제한 사항

  • 1≤1 \le queries.length ≤100,000\le 100{,}000
  • queries[i] = [n, r], 0≤r≤n≤1060 \le r \le n \le 10^6

기대 복잡도

시간
O(MAX_N + Q)
공간
O(MAX_N)

입출력 예

queries기대 출력
[[5,2],[10,0],[10,10],[6,3]][10,1,1,20]
[[1000000,500000]][996692777]

힌트

힌트

(nr)=n!r! (n−r)!\binom{n}{r} = \dfrac{n!}{r!\,(n-r)!}이지만, 나머지 세계에서는 나눗셈을 그대로 할 수 없습니다. 대신 역원을 곱합니다.

1,000,000,0071{,}000{,}000{,}007은 소수이므로 페르마의 소정리에 따라 a−1≡ap−2(modp)a^{-1} \equiv a^{p-2} \pmod p입니다.

  1. fact[i] = i! mod p를 10610^6까지 미리 구합니다.
  2. inv_fact[MAX] = fact[MAX]^(p-2)를 거듭제곱으로 한 번만 구하고, inv_fact[i-1] = inv_fact[i] · i로 거꾸로 채웁니다.
  3. 질의마다 fact[n] · inv_fact[r] · inv_fact[n-r](곱할 때마다 나머지)을 O(1)O(1)에 답합니다.

곱하기 전 값이 pp 미만이면 곱이 101810^{18} 근처라 64비트에 들어갑니다.

복잡도 목표

질의마다 r번 곱하고 나누는(역원을 매번 구하는) 풀이는 O(Q⋅N)O(Q \cdot N) 이상이라 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251578 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness405판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.