[백준 13977] 이항 계수와 쿼리 (C++)

문제 링크: https://www.acmicpc.net/problem/13977

13977번: 이항 계수와 쿼리

1. 주의할 점

- 입출력 속도 함수를 사용해야 한다 (cin, cout의 경우 사용하지 않으면 TLE 발생)

- 매 TC마다 Factorial을 구하지 않고 미리 구해놓는다

- 페르마의 소정리에 대해 알고 있어야 한다

 

2. 구현

*공통 부분

- My_pow(Num, Remain) 함수를 직접 구현하여 Pow함수를 LogN번 안에 계산하도록 한다(분할 정복). 라이브러리에 있는 Pow함수는 N의 시간복잡도를 가져서 느리다

 

1) Factorial[]만 미리 구해놓는 방법 (208ms)

- 최대 400만개이다 보니 매번 Factorial을 구하려고 하면 TLE발생한다

- 페르마의 소정리에 의해 분수의 분자를 Up, 분모를 Down으로 설정하고 각 Factorial을 먼저 구한다. 이후, Down의 값이 분자와 곱해지기 위해 페르마의 소정리에 의해 Down = My_pow(Down, MOD-2)로 변형된다. 

- Up*Down을 MOD로 나눴을 때 나머지를 출력한다

 

#include <iostream>
using namespace std;
long long factorial[4000001];
long long MOD = 1000000007;

long long my_pow(long long num, long long remain) {
	if (remain == 0) return 1;
	else if (remain == 1) return num;
	if (remain % 2 == 0) {
		long long temp = my_pow(num, remain / 2);
		return (temp*temp) % MOD;
	}
	else if (remain % 2 == 1) {
		long long temp = my_pow(num, remain - 1);
		return (temp*num) % MOD;
	}
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
	int m, n, k;
	cin >> m;
	factorial[0] = 1;
	for (int i = 1; i < 4000001; i++) {
		factorial[i] = factorial[i - 1] * i;
		factorial[i] %= MOD;
	}
	
	for (int i = 0; i < m; i++) {
		cin >> n >> k;
		long long up = factorial[n];
		long long down = (factorial[k] * factorial[n - k]) % MOD;
		down = my_pow(down, MOD - 2) % MOD;
		cout << (up*down) % MOD << '\n';
	}
	return 0;
}

 

2) Factorial[], Rev[]를 미리 구해놓는 방법 (208ms)

- 잘 보면 매 TC마다 위에 파란색으로 칠한 My_pow 함수를 통해 Down을 갱신시켜야 한다

- 위의 것을 미리 Rev[]배열에 저장시켜 계산 속도를 줄여보려고 했지만 TC가 훨씬 많아야 차이가 날것 같다(둘다 현재 TC로는 속도 차이가 없다) 

 

#include <iostream>
using namespace std;
long long factorial[4000001];
long long rev[4000001];
long long MOD = 1000000007;

long long my_pow(long long num, long long remain) {
	if (remain == 0) return 1;
	else if (remain == 1) return num;
	if (remain % 2 == 0) {
		long long temp = my_pow(num, remain / 2);
		return (temp*temp) % MOD;
	}
	else if (remain % 2 == 1) {
		long long temp = my_pow(num, remain - 1);
		return (temp*num) % MOD;
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int m, n, k;
	cin >> m;
	factorial[0] = 1;
	for (int i = 1; i < 4000001; i++) {
		factorial[i] = factorial[i - 1] * i;
		factorial[i] %= MOD;
	}
	rev[4000000] = my_pow(factorial[4000000], MOD - 2) % MOD;
	for (int i = 3999999; i >= 0; i--)
		rev[i] = (rev[i + 1] * (i + 1)) % MOD;
	for (int i = 0; i < m; i++) {
		cin >> n >> k;
		long long up = factorial[n];
		long long down = rev[k];
		down *= rev[n - k];
		down %= MOD;
		cout << (up*down) % MOD << '\n';
	}
	return 0;
}