`
다른 분의 풀이를 보고 이전 값의 제곱 값에 $_{2^{i+1}-2} \mathrm{C}_{2^i-1}$ 를 곱하는 원리 찾음
해당하는 조합 숫자는 파스칼의 삼각형 원리 이용
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class B13912 {
static final long R = 1000000007;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int h = Integer.parseInt(br.readLine());
long[] dp = new long[11];
long[][] arr = new long[2048][2048];
arr[0][0] = 1;
for(int i=1;i<2048;i++) { // 삼각형 방식으로 값을 넣어 파스칼의 삼각형 생성
arr[i][0] = 1;
for(int j=1;j<=i;j++) {
arr[i][j] = (arr[i-1][j] + arr[i-1][j-1])%R;
}
}
dp[0] = 1;
for(int i=1;i<=h;i++) {
dp[i] = (dp[i-1]*dp[i-1]) % R; // 제곱 후 새로운 값 곱해주기
dp[i] *= arr[(1<<(i+1))-2][(1<<i)-1];
dp[i] %=R;
}
System.out.println(dp[h]);
}
}
|