`divide and conquer
1과 4 사이의 숫자 조합 개수를 출력하는 문제(2의 거듭제곱)
- 처음에 divide(x/2) * divide(x/2) * (x%2+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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class B18291 {
static int T,N;
static final long m = 1000000007;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
T = Integer.parseInt(br.readLine());
for(int tc=0;tc<T;tc++) {
N = Integer.parseInt(br.readLine());
sb.append(N==1?1:divide(N-2)).append("\n");
}
System.out.println(sb);
}
private static long divide(int x) {
if(x==0) return 1;
long temp = divide(x/2);
return temp*temp*(x%2+1)% m;
}
}
|