문제
https://www.acmicpc.net/problem/19575
문제해설
다항식이 주어지고 다항식을 계산한 값에
1000000007 나눈 나머지를 구하면 된다.
문제풀이
차수가 최대 10^6까지 오기때문에
단순히 pow함수등을 이용해 앞에서부터 제곱을 하며 구한다면
시간초과가 날 것이다.
그렇기때문에 문제에 나온 힌트를 이용해서 접근해야 한다.
호너의 방법을 구현하면 풀린다.
미리 첫번째 수를 합에 넣어놓고
두번째부터 합에 들어있던 값에 x를 곱해주고 a를 더해준다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<algorithm>
#include<vector>
#define mod 1000000007
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, x; cin >> n >> x;
ll sum = 0;
for (int i = 0; i < n + 1; i++) {
int a, b; cin >> a >> b;
if (i == 0)
sum = a;
else {
sum = (sum * x + a) % mod;
}
}
cout << sum;
return 0;
}