UVa 498 Polly the Polynomial

题目描述题目要求计算多项式在多个xxx值处的取值。多项式系数按c0xnc1xn−1⋯cnc_0 x^n c_1 x^{n-1} \dots c_nc0​xnc1​xn−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{Horners method}Horner’s method可以高效计算。霍纳方法对于多项式P(x)c0xnc1xn−1⋯cnP(x) c_0 x^n c_1 x^{n-1} \dots c_nP(x)c0​xnc1​xn−1⋯cn​可改写为P(x)(…((c0xc1)xc2)x… )xcn P(x) (\dots ((c_0 x c_1)x c_2)x \dots )x c_nP(x)(…((c0​xc1​)xc2​)x…)xcn​计算时从最高次项开始每次乘以xxx并加上下一项系数只需nnn次乘法和nnn次加法。算法步骤对于每个xxx初始化sum0\textit{sum} 0sum0。从系数列表的第一个元素c0c_0c0​开始依次更新sumsum×xci\textit{sum} \textit{sum} \times x c_isumsum×xci​。最终sum\textit{sum}sum即为多项式值。注意点系数列表长度即为n1n1n1。注意输入中可能有负号与数字相连如-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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);istringstream iss;vectorlonglongcoefficients;string line;while(getline(cin,line)){iss.clear();iss.str(line);coefficients.clear();longlongnumber;while(issnumber)coefficients.push_back(number);getline(cin,line);iss.clear();iss.str(line);boolfirsttrue;while(issnumber){longlongsum0,base1;for(inticoefficients.size()-1;i0;i--){sumbase*coefficients[i];base*number;}if(first)firstfalse;elsecout ;coutsum;}cout\n;}return0;}