秦九韶算法

秦九韶算法可以在 $O(n)$ 的时间内计算一个多项式的值。

考虑多项式

$f(x)=\sum_{i=0}^na_ix^i$

如果直接暴力：

int Sum(int x){
	int ans=0;
	for(int i=0;i<=n;i++){
		int res=a[i];
		for(int j=0;j<=i;j++)res*=x;
		ans+=res;
	}
	return ans;
}

显然是 $O(n^2)$ 的>_<

如果用快速幂可以加速到 $O(n\log n)$，但是还是不够快的说qwq

考虑下面这个等式：

$\begin{aligned} &a_0+a_1x+a_2x^2+\cdots+a_nx^n\\ =&a_0+x(a_1+a_2x+a_3x^2+\cdots+a_nx^{n-1})\\ =&a_0+x(a_1+x(a_2+a_3x+a_4x^2_\cdots+a_nx^{n-2})\\ =&\cdots\\ =&a_0+x(a_1+x(a_2+x(a_3+\cdots+x(a_{n-1}+xa_n)))) \end{aligned}$

诶，如果我们先把 $a_n$ 乘上 $x$，加上 $a_{n-1}$，再乘 $x$ ，再加上 $a_{n-2}$，再乘 $x$ ......一直这么算下去，就能算出来多项式的值qwq！

这，这是 $O(n)$ 的qwq！

代码也很简洁：

int Sum(int x){
	int ans=0;
	for(int i=n;i>=1;i--){
		ans+=a[i];
		ans*=x;
	}
 	ans+=a[0];
	return ans;
}