题目描述
题目要求计算多项式在多个xxx值处的取值。多项式系数按c0xn+c1xn−1+⋯+cnc_0 x^n + c_1 x^{n-1} + \dots + c_nc0xn+c1xn−1+⋯+cn的顺序给出（nnn为多项式的次数）。对于每组数据，输出每个xxx对应的多项式值。
输入格式
输入包含偶数行，每对相邻行表示一个测试用例：第一行是多项式的系数列表（整数），第二行是xxx值的列表（整数）。输入以文件结束符（EOF\texttt{EOF}EOF）终止。
输出格式
对于每个测试用例，输出一行，包含每个xxx对应的多项式值，之间用空格分隔。
样例
输入
-2 -5 0 1 6 -1 -7 6 -1输出
-2 -2 -2 -2 -2 -2 -2 -6 5 -2题目分析
本题的核心是多项式求值。直接使用霍纳方法（Horner’s method\texttt{Horner's method}Horner’s method）可以高效计算。
霍纳方法
对于多项式P(x)=c0xn+c1xn−1+⋯+cnP(x) = c_0 x^n + c_1 x^{n-1} + \dots + c_nP(x)=c0xn+c1xn−1+⋯+cn，可改写为：
P(x)=(…((c0x+c1)x+c2)x+… )x+cn P(x) = (\dots ((c_0 x + c_1)x + c_2)x + \dots )x + c_nP(x)=(…((c0x+c1)x+c2)x+…)x+cn
计算时从最高次项开始，每次乘以xxx并加上下一项系数，只需nnn次乘法和nnn次加法。
算法步骤
- 对于每个xxx，初始化sum=0\textit{sum} = 0sum=0。
- 从系数列表的第一个元素（c0c_0c0）开始，依次更新sum=sum×x+ci\textit{sum} = \textit{sum} \times x + c_isum=sum×x+ci。
- 最终sum\textit{sum}sum即为多项式值。
注意点
- 系数列表长度即为n+1n+1n+1。
- 注意输入中可能有负号与数字相连，如
-2表示整数−2-2−2。
复杂度分析
每个xxx计算O(n)O(n)O(n)次，总复杂度O(m×n)O(m \times n)O(m×n)。
代码实现
// Polly the Polynomial// UVa ID: 498// Verdict: Accepted// Submission Date: 2016-07-16// UVa Run Time: 0.070s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);istringstream iss;vector<longlong>coefficients;string line;while(getline(cin,line)){iss.clear();iss.str(line);coefficients.clear();longlongnumber;while(iss>>number)coefficients.push_back(number);getline(cin,line);iss.clear();iss.str(line);boolfirst=true;while(iss>>number){longlongsum=0,base=1;for(inti=coefficients.size()-1;i>=0;i--){sum+=base*coefficients[i];base*=number;}if(first)first=false;elsecout<<' ';cout<<sum;}cout<<'\n';}return0;}
)
