8058 : 이항 계수 쿼리
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$n$개의 쿼리가 주어집니다. 각 쿼리마다 두 정수 $a$와 $b$가 주어질 때, 이항 계수 $\binom{a}{b} \pmod{10^9+7}$의 값을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le n \le 100{,}000$
• $0 \le b \le a \le 1{,}000{,}000$
[제약 조건]
• $1 \le n \le 100{,}000$
• $0 \le b \le a \le 1{,}000{,}000$
입력 설명
첫째 줄에 쿼리의 개수 $n$이 주어집니다. ($1 \le n \le 100{,}000$)
다음 $n$개의 줄에 걸쳐 두 정수 $a, b$가 공백으로 구분되어 주어집니다. ($0 \le b \le a \le 1{,}000{,}000$)
다음 $n$개의 줄에 걸쳐 두 정수 $a, b$가 공백으로 구분되어 주어집니다. ($0 \le b \le a \le 1{,}000{,}000$)
출력 설명
각 쿼리에 대해 $\binom{a}{b} \pmod{10^9+7}$의 결과를 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
5 3
10 2
15 15
출력 예시
COPY
복사되었습니다!
복사되었습니다!
10
45
1도움
$\binom{a}{b} = \frac{a!}{b!(a-b)!} \pmod p$ 공식을 사용합니다. 팩토리얼($a!$) 배열과 팩토리얼의 모듈러 곱셈 역원 배열을 미리 $O(MAX)$에 구한 뒤, 각 쿼리를 $O(1)$에 계산하여 전체 시간 복잡도 $O(MAX + n)$에 해결할 수 있습니다.