Baekjoon 19575 Polynomial JAVA

19575번: Polynomial

문제

경근이는 수학을 좋아한다. 수학을 너무 좋아하는 나머지 다항식을 빠르게 평가하는 프로그램을 작성했다. 미지수 x로 구성된 다항식 f(x)에서 x에 k를 대입하여 f(k)를 구하는 것을 평가라고 한다. 하지만, 경근이가 작성한 프로그램은 다항식의 각 항을 평가해서 합치는 식으로 짜여 있었기 때문에, 한 번 다항식을 평가할 때마다 차수의 제곱에 비례한 만큼의 시간이 걸렸다. 경근이는 계산 시간을 조금이라도 줄이기 위해, 다항식 평가 알고리즘을 개선하여 성능을 최적화하기로 한다.

경근이가 생각한 아이디어는 이렇다. “값을 더하고, 계수를 곱하고, 값을 더하고, 계수를 곱하는 것을 반복하면 어떨까?”

예를 들면, x^4 + 2x^3 + 3x^2 + 4x + 5는 경근이가 작성한 프로그램대로 계산한다면 덧셈 4회, 곱셈 9회의 연산이 필요하지만, 경근이가 생각한 대로라면 앞의 다항식을 x(x(x(x + 2) + 3) + 4) + 5로 바꿀 수 있으며, 덧셈 4회 곱셈 3회로 연산량이 대폭 줄어드는 셈이다.

경근이를 도와 다항식 계산 프로그램을 개선한 버전을 제출하도록 하자. 다항식 계산 프로그램의 성능을 개선하면 시간 초과가 뜨지 않는다.

 

입력

첫 번째 줄에는 다항식의 차수 N, 평가할 값인 정수 x가 주어진다. (1 ≤ N ≤ 106, 0 ≤ x ≤ 108)

두 번째 줄부터 N + 2번째 줄까지 다항식의 각 항에 대한 정보인 Ai, i가 각각 입력으로 주어진다. Ai는 항의 계수이며, i는 항의 차수이다. 항의 계수는 0 이상 100 이하의 정수이다.

항의 차수는 두 번째 줄부터 N + 2번째 줄까지 각각 N, N − 1, ..., 0이다.

출력

다항식을 평가한 후 109 + 7로 나눈 나머지를 출력한다.

풀이

주어진 문제 조건에 따라서 입력받는 식을 나누어서 계산한다.

mod연산은 각 연산의 중간에 쓰더라도 나머지 연산 특징에 의해서 몫을 건들이지 않고 나머지에만 영향을 주게된다

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken()), x=Integer.parseInt(st.nextToken());
		long ans=0;
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			ans+=Integer.parseInt(st.nextToken());
			ans*=x;
			ans%=(1000000007);
		}
		st = new StringTokenizer(br.readLine());
		ans+=Integer.parseInt(st.nextToken());
		System.out.println(ans);
	}
}