[Silver I] 謎紛芥索紀 (Large) - 14731
성능 요약
메모리: 37048 KB, 시간: 292 ms
분류
미적분학, 분할 정복을 이용한 거듭제곱, 수학
제출 일자
2024년 6월 17일 23:59:48
문제 설명
성민이는 이번 학기에 미적분학 과목을 수강하고 있다. 다항함수의 미분 단원 과제를 하던 도중 미분을 하기가 귀찮아진 성민이는 미분하려는 함수 f(x)가 주어지면, 미분 된 함수 f’(x)를 자동으로 구해주는 프로그램을 만들어서 계산을 줄일 생각을 하였다. 우리도 성민이가 원하는 프로그램을 한번 같이 만들어보도록 하자.
입력
첫째 줄에는 항의 개수 N(1 ≤ N ≤ 100000)이 주어진다.
둘째 줄부터 N개 줄에 걸쳐서 항의 계수 C(0 < C ≤ 100)와 항의 차수 K(0 ≤ K ≤ 109)가 항의 차수와 관계 없이 무작위로 주어진다. 항의 차수가 같은 항은 2개 이상 존재하지 않는다
출력
f’(2)의 값을 109+7로 나눈 나머지를 첫째 줄에 출력한다.
접근 방법
0. 모듈러연산을 기반으로 한다.
1. 입력 받은 값을 1_000_000_007 MOD로 선언하고 나누어주면서 계산을 한다.
2. 항의 계수 C와 항의 차수 K를 곱하고 MOD로 나누어준다.
3. 항의 차수인 K에서 -1을 뺀 값에 대한 2의 제곱수를 구해준다. 이 때 시간 절약을 위해 분할 정복을 이용한다. (log N)
4. 그 후 나온 값 또한 MOD 범위를 초과할 수 있으므로 나머지를 구해준다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* 경과 시간 : 35분
*/
public class BOJ_14731 {
static final long MOD = 1_000_000_007;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long answer = 0;
StringTokenizer st;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
long c = Long.parseLong(st.nextToken());
long k = Long.parseLong(st.nextToken());
answer = (answer + (c * k % MOD) * pow(k - 1)) % MOD;
}
System.out.println(answer);
}
private static long pow(long expo) {
if (expo == -1) return 0;
long answer = 1, base = 2;
while (expo != 0) {
if (expo % 2 != 0) {
answer = answer * base % MOD;
expo--;
}
expo >>= 1;
base = base * base % MOD;
}
return answer;
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 14716번 : 현수막 Silver1(실버1) - JAVA[자바] (1) | 2024.01.29 |
---|---|
[백준] 1309번 : 동물원 Silver1(실버1) - JAVA[자바] (1) | 2024.01.28 |
[백준] 1326번 : 폴짝폴짝 Silver2(실버2) - JAVA[자바] (1) | 2024.01.24 |
[백준] 1389번 : 케빈 베이컨의 6단계 법칙 Silver1(실버1) - JAVA[자바] (0) | 2024.01.16 |
[백준] 11403번 : 경로 찾기 Silver1(실버1) - JAVA[자바] (0) | 2024.01.16 |