用C++编写算法，输入整数n(1<=n<=1000)，x(1<=x<=1000)和ai（i=0,1,2,3，…n）的值，设计时间复杂度小于O(n2)的算法，求一元多项式 的值

在C++中，为了计算一元多项式`P(x) = a0 + a1 * x + a2 * x^2 + ... + an * x^n`的值，你可以利用二分查找的思想，因为对于每个系数`a_i`，实际上只关心它对应的`x^(i)`项。由于指数`i`不会超过`n`，所以我们可以用`log n`的时间复杂度来找到`x^i`的位置。这是一种称为“快速幂”（Fast Exponentiation）的技术，可以将乘法运算的时间复杂度降低到对数级别。

以下是简单的步骤：

1. 定义一个函数`fastPower(x, n)`用于计算`x`的n次方，通过迭代实现快速幂，时间复杂度为`O(log n)`。
2. 再定义一个函数`evaluatePolynomial(a, n, x)`接受数组`a`、长度`n`以及变量`x`，遍历数组，每次将当前`x`值乘以前面各项的系数并累加起来，同时利用`fastPower(x, i)`来计算对应指数项。

下面是基本的伪代码实现：

double fastPower(double base, int exponent) {
    if (exponent == 0) return 1;
    double result = fastPower(base, exponent / 2);
    result *= result; // 如果是偶数次方
    if (exponent % 2) result *= base; // 如果是奇数次方
    return result;
}

double evaluatePolynomial(double* coefficients, int n, double x) {
    double sum = coefficients[0];
    for (int i = 1; i <= n; ++i) {
        sum += coefficients[i] * fastPower(x, i);
    }
    return sum;
}