다항식
면접 대비시간 제한1초메모리 제한1024 MB
다항식의 계수와 차수가 내림차순으로 주어질 때, 호너 방법으로 x에서의 값을 계산해 1e9+7로 나눈 나머지를 출력한다.
문제
경근이는 수학을 좋아한다. 수학을 너무 좋아한 나머지 다항식을 빠르게 평가하는 프로그램을 작성했다. 미지수 x로 이루어진 다항식 f(x)에서 x에 k를 대입해 f(k)를 구하는 것을 평가라고 한다. 그런데 경근이가 작성한 프로그램은 다항식의 각 항을 따로 평가해서 더하는 방식이라, 다항식을 한 번 평가할 때마다 차수의 제곱에 비례하는 시간이 걸렸다. 경근이는 계산 시간을 조금이라도 줄이기 위해 다항식 평가 알고리즘을 개선해 성능을 최적화하려 한다.
경근이가 떠올린 방법은 이렇다. "값을 더하고, 계수를 곱하고, 값을 더하고, 계수를 곱하기를 반복하면 어떨까?"
예를 들어 x4 + 2x3 + 3x2 + 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로 나눈 나머지를 출력한다.
힌트
입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간 초과가 날 수 있다.
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로 제출하는 것을 권장한다.