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;
}