레야몬
[C++] 13977번 이항 계수와 쿼리 - 수학, 정수론, 조합론, 분할 정복을 이용한 거듭제곱, 모듈로 곱셈 역원, 페르마의 소정리 본문
알고리즘/백준
[C++] 13977번 이항 계수와 쿼리 - 수학, 정수론, 조합론, 분할 정복을 이용한 거듭제곱, 모듈로 곱셈 역원, 페르마의 소정리
Leyamon 2022. 12. 3. 12:491. 문제
- M개의 자연수 N과 정수 K가 주어졌을 때 이항 계수 \(_{n}C_{k}\)를 \(1,000,000,007\)로 나눈 나머지를 구하는 프로그램을 작성하시오
<입력>
- - 1 - \(M(1 \leq M \leq 100,000)\)
- - M개의 줄 - \(N, K(1 \leq N \leq 4,000,000, 0 \leq K \leq N)\)
<출력>
- M개의 줄에 \(_{n}C_{k}\)를 \(1,000,000,007\)로 나눈 나머지를 출력한다.
2. 재정의
- X
3. 해결 방법
- factorial값을 모두 저정한 다음 페르마의 소정리를 이용해 간단하게 풀면 된다.
4. 실수한 점, 개선할 점
- 항상 나오지만 자료형 범위 조심하자
- 분할 정복 사용할 때 재귀 함수를 사용하지 않고 반복문을 이용해하는 방법도 있었다. 이렇게 한 코드가 있어서 아래에 참고하였다.
- 또 fastio로 매크로를 사용해서 위로 올리니까 코드가 보기 깔끔해진 것 같다.
<코드>
#include <iostream>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 4000001;
const int mod = 1000000007;
// <문제>
// 쿼리의 개수 M, NCK
ll M, N, K;
// 팩토리얼
int fact[MAX_N];
ll Pow(ll a, int b) {
ll ret = 1;
while(b) {
if(b & 1)
ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}
void input() {
cin >> M;
fact[0] = 1;
for(int i=1; i<MAX_N; i++)
fact[i] = 1ll*fact[i-1] * i % mod;
}
int main() {
fastio;
input();
for(int i=0; i<M; i++) {
cin >> N >> K;
cout << fact[N] * Pow(1ll*fact[K] * fact[N-K] % mod, mod-2) % mod << '\n';
}
return 0;
}
<참고한 코드>
https://www.acmicpc.net/board/view/86891
글 읽기 - const 키워드 쓴다고 2배나 속도가 차이가 나나요?
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
<문제 바로가기>
https://www.acmicpc.net/problem/13977
13977번: 이항 계수와 쿼리
\(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
www.acmicpc.net
※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.
'알고리즘 > 백준' 카테고리의 다른 글
[C++] 1655번 가운데를 말해요 - 자료 구조, 우선순위 큐 (0) | 2022.12.06 |
---|---|
[C++] 10830번 행렬 제곱 - 수학, 분할 정복, 분할 정복을 이용한 거듭제곱, 선형대수학 (0) | 2022.12.06 |
[C++] 11402번 이항 계수 4 - 수학, 다이나믹 프로그래밍, 정수론, 조합론, 뤼카 정리 (0) | 2022.12.03 |
[C++] 11401번 이항 계수 3 - 수학, 정수론, 조합론, 분할 정복을 이용한 거듭제곱, 모듈로 곱셈 역원, 페르마의 소정리 (0) | 2022.12.02 |
[C++] 10986번 나머지 합 - 수학, 누적 합 (0) | 2022.12.02 |
Comments