Baekjoon 19575번 Polynomial

문제

https://www.acmicpc.net/problem/19575

걸린 시간

00 : 46 : 43

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, x;
    cin >> n >> x;
    vector<int> p(n+1); // polynomial
    int c, d; // 계수 차수
    for(int i = 0; i < n+1; i++){
        cin >> c >> d;
        p[d] = c;
    }
    long long ans = 0; 
    for(int i = n; i > 0; i--)
        ans = ((ans+p[i])*x)%1000000007;
    ans += p[0];
    cout << ans << "\n";
    return 0;
}

문제에서 설명해준 평가 알고리즘을 그대로 구현하면 된다.

다항식의 차수 n, 평가할 값 x 가 상당히 큰 수이므로 각 단계의 결과값을 10⁹+7 으로 나눈 나머지를 출력하도록 한다.

중간 계산에서 산술 오버플로가 발생하지 않도록 하려면 long long 자료형을 사용해야한다.