15级算法第一次上机解题报告

15级算法第一次上机解题报告

A 多项式计算器

解题思路：

求多项式的值，很典型的秦九韶算法的应用。如果使用朴素算法，每次算一个，枚举，对于每个i都要进行(i+1)次乘法，复杂度为O()，n在10000范围时显然会超时。可以对算的过程进行复用，记录下每次的，下一次的就由这个得到，复杂度降为O(n)。

更优的方法是秦九韶算法：

将

改写为：

记=,

取=

则即为多项式的值。

使用秦九韶算法求n次多项式值时，至多进行n次乘法和n次加法，十分高效。

此题中还要注意的是，运算过程中可能会超出int范围，全程long long并且及时取模即可。

代码：

#include <iostream>using namespace std;const int MaxT = 10000 + 7;
const long long mod = (int) 1e6 + 7;
int n, x, t, T = 0;
long long ans;
long long a[MaxT];int main() {while (cin >> n >> x >> t) {T++;cout << "Case #" << T << ":n";while (t--) {for (int i = 0; i <= n; i++) cin >> a[i];  //读入系数ans = a[n] % mod;for (int i = n - 1; i >= 0; i--) {  //秦九韶算法ans *= x;ans += a[i];ans %= mod;}cout <<