Lv.3combinatoricsmathmodular-inverse
조합의 수 질의
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
각 질의 queries[i] = [n, r]에 대해 서로 다른 n개 중 r개를 고르는 방법의 수 를 로 나눈 나머지를 구해,
질의 순서대로 배열에 담아 반환하세요.
입출력 예
| queries | result |
|---|---|
[[5, 2], [10, 0], [10, 10], [6, 3]] | [10, 1, 1, 20] |
[[1000000, 500000]] | [996692777] |
입출력 예 설명
예 1 — , , 입니다.
예 2 — 실제 값은 30만 자리가 넘는 수지만 나머지만 구하면 됩니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(queries: int[][]) → int[]
제한 사항
-
queries.length queries[i] = [n, r],
기대 복잡도
- 시간
- O(MAX_N + Q)
- 공간
- O(MAX_N)
입출력 예
| queries | 기대 출력 |
|---|---|
[[5,2],[10,0],[10,10],[6,3]] | [10,1,1,20] |
[[1000000,500000]] | [996692777] |
힌트
힌트
이지만, 나머지 세계에서는 나눗셈을 그대로 할 수 없습니다. 대신 역원을 곱합니다.
은 소수이므로 페르마의 소정리에 따라 입니다.
fact[i] = i! mod p를 까지 미리 구합니다.inv_fact[MAX] = fact[MAX]^(p-2)를 거듭제곱으로 한 번만 구하고,inv_fact[i-1] = inv_fact[i] · i로 거꾸로 채웁니다.- 질의마다
fact[n] · inv_fact[r] · inv_fact[n-r](곱할 때마다 나머지)을 에 답합니다.
곱하기 전 값이 미만이면 곱이 근처라 64비트에 들어갑니다.
복잡도 목표
질의마다 r번 곱하고 나누는(역원을 매번 구하는) 풀이는 이상이라 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1578 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 2 | 입력·출력 공개 |
| correctness | 40 | 5 | 판정만 |
| performance | 60 | 4 | 판정만 |