BOJ13977 이항 계수와 쿼리

www.acmicpc.net/problem/13977

13977번: 이항 계수와 쿼리

=

16134 조합(Combination)

15791 세진이의 미팅

 

• 페르마의 소정리에 의해

• p가 소수이고 a가 정수일 때, a^p≡a (mod p)
  ⇒ a^(p-1)≡1 (mod p)
  ⇒ a^(p-2)*a≡1 (mod p)
  즉 mod p에서 a의 역원이 a^(p-2)가 된다.

 

 

• a^p구하는 건 재귀함수로 해주고

• long long 주의

• 13977번의 경우 N!, K!, (N-K)!을 모두 구해야하니까 while 돌리기 전에 1부터 MAX까지 구해놓는다

• 16134, 15791번은 N!/(N-K)!(=nPk)와 K!만 구하면 되니까 K를 작은 거로 바꾸고 계산해주자

 

코드

//combination
//=BOJ15791
//=BOJ13977
#include <iostream>
#include <algorithm>
using namespace std;

long long P = 1000000007;
long long mod[4000001] = { 0, };
long long pow(long long a, int k) {
	if (k == 1) return a;

	long long ra = pow(a, k / 2);
	if (k % 2) return (a * ((ra * ra) % P)) % P;
	else return (ra * ra) % P;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	mod[2] = 2;
	for (int i = 3; i < 10; ++i) mod[i] = mod[i - 1] * i;
	long long tmp = mod[9];
	for (int i = 10; i < 4000001; ++i) tmp *= i, tmp %= P, mod[i] = tmp;

	int M; cin >> M;
	while (M--) {
		int N, K1;
		cin >> N >> K1;
		int K2 = N - K1;
		if (K1 > K2) swap(K1, K2);
		if (K1 == 0) { cout << "1\n"; continue; }
		if (K1 == 1) { cout << N << "\n"; continue; }

		long long A = mod[N], B = mod[K1], C = mod[K2];

		A *= pow(B, (int)P - 2); A %= P;
		A *= pow(C, (int)P - 2); A %= P;
		cout << A << "\n";
	}
	return 0;
}

이거 코드 예쁘게 어떻게 하는 거지..? 했다..!! 공부할 게 많은 티스토리,,허