문제
https://www.acmicpc.net/problem/18291
문제해설
비요뜨가 먹고싶어지는 문제
테스트케이스 t가 주어지고 n이 주어진다.
1에서 시작해서 n까지 갈 수 있는 경우의 수를 구하면 된다.
한번에 이동할 수 있는 칸은 최대 n까지 가능하다.
문제풀이
dp문제답게 그냥 1부터 해보게되면 n번째까지 가는 경우는 2^(n-2)가 나온다는 것을 알 수 있다.
다만 n의 범위가 10억까지이기 때문에 제곱을 분할정복을 이용해 구해야한다.
이 방법은 https://www.acmicpc.net/problem/1629에 사용된 방법을 그대로 사용했다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
using namespace std;
typedef long long ll;
ll big = 1e9 + 7; // 이번에 처음써본 표기법 1e3 = 10^3
int pow(int a, int b) {
if (b == 0)
return 1;
else if (b % 2 == 0) {
ll mul = pow(2, b / 2);
return mul * mul % big;
}
else {
ll mul = pow(2, b / 2);
ll temp = mul * mul % big;
return a * temp % big;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
if (n == 1)
cout << 1 << "\n";
else
cout << pow(2, n - 2) << "\n";
}
return 0;
}