19575번 - Polynomial

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

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

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

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

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

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

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

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

입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다.

C++을 사용하고 있고 cin/cout을 사용하고자 한다면, cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 개행문자(\n)를 쓰자. 단, 이렇게 하면 더 이상 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다.

Java를 사용하고 있다면, Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용할 수 있다. BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다.

Python을 사용하고 있다면, input 대신 sys.stdin.readline을 사용할 수 있다.

마지막으로, Pypy3은 Python 3와 같은 문법을 가지면서 일반적으로 더 빠르게 동작한다. 연산량이 많은 문제에서 Python을 사용하고자 한다면 Pypy로 제출하는 것을 권장한다.