[백준] 11401번 _ 이항 계수 3

 


1. 문제

https://www.acmicpc.net/problem/11401

2. 풀이

2.1. 시간 초과 풀이

  • hello 라는 함수가 홀수일 때는 y/2, 1+y/2 로 분기되고, 짝수일 때는 y/2와 y/2 로 분기됩니다. 이러한 방식은 제곱 수에 1000000005가 들어와서 $ \log_2^{1000000005} = 29.89 $ 정도의 높이를 가지게 되고, 완전 트리라고 가정하면 노드 수는 약 $ 2^{31} - 1 $ 개가 됩니다.
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#define P 1000000007
using namespace std;
int n, k;
long long  f[4000001];
long long hello_arr[1000000007+1];
long long ans;

long long hello(int x, int y) {
	if (y == 1) return x % P;
	if (hello_arr[y])  return hello_arr[y];

	if (y % 2 == 0) {
		hello_arr[y] = (hello(x, y / 2) * hello(x, y / 2)) % P;
		return hello_arr[y];
	}
	else {
		hello_arr[y] = (hello(x, y / 2) * hello(x, 1 + y / 2)) % P;
		return hello_arr[y];
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> k; 
	f[0] = f[1] = 1;
	// make factorial array
	for (int i = 2; i <= n; i++)		
		f[i] = (f[i - 1] * i) % P;
	
	long long temp = (f[k] * f[n - k]) % P;
	ans = hello(temp, P - 2);
	ans = (f[n] * ans) % P;
	cout << ans;
}

2.2. 메모이제이션을 이용한 풀이

  • 위와 풀이 방법은 동일하지만 나온 값은 map에 적어두고 사용하여, 다시 꺼낼 때 자식을 거치지 않고 바로 return 을 할 수 있게 합니다.
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <map>
#include <iostream>
#define P 1000000007
using namespace std;
int n, k;
long long  f[4000001];
map<long long, long long> hello_arr;
long long ans;

long long hello(int x, int y) {
	if (y == 1) return x % P;

	map<long long, long long>::iterator iter;
	iter = hello_arr.find(y);
	if (iter != hello_arr.end())	return hello_arr[y];

	if (y % 2 == 0) {
		hello_arr[y] = (hello(x, y / 2) * hello(x, y / 2)) % P;
		return hello_arr[y];
	}
	else {
		hello_arr[y] = (hello(x, y / 2) * hello(x, 1 + y / 2)) % P;
		return hello_arr[y];
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> k; 
	f[0] = f[1] = 1;
	// make factorial array
	for (int i = 2; i <= n; i++)		
		f[i] = (f[i - 1] * i) % P;
	
	long long temp = (f[k] * f[n - k]) % P;
	ans = hello(temp, P - 2);
	ans = (f[n] * ans) % P;
	cout << ans;
}

2.3. 메모이제이션을 사용하지 않은 풀이

  • p 함수에 제곱수가 짝수가 들어오면 한 번의 p/2 함수만 호출하고, 홀수가 들어오면 1을 빼주어 짝수를 만들어 주는 식으로 계속해서 진행합니다.
#define _CRT_SECURE_NO_WARNINGS
#include<algorithm>
#include<iostream>
#define P 1000000007
using namespace std;
int n, k;
long long f[4000001];
long long ans;

long long p(long long x, long long y) {
	if (y == 1)			return x;         //x값이 최대 400만이라 %M연산 안해도 됨
	if (y % 2 == 1)	return (p(x, y - 1) * x) % P;
	else {
		long long temp = p(x, y / 2);
		return (temp * temp) % P;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> k;
	f[0] = f[1] = 1;
	for (int i = 2; i <= n; i++)
		f[i] = (f[i - 1] * i) % P;

	long long tmp = (f[k] * f[n - k]) % P;
	ans = p(tmp, P - 2);
	ans = (f[n] * ans) % P;
	cout << ans;
}