给定 $n$ 个坐标 $(x_i,y_i)$，求解唯一确定的最高次不超过 $n-1$ 次的多项式 $f(x)$，满足 $f(x_i)=y_i$。

洛谷p4781

构造 $g_i(x)=y_i\prod_{j\neq i}\frac {x-x_j}{x_i-x_j}$，易知

$$g_i(x_j)= \begin{cases} y_i, & j=i \\ 0, & j\neq i \end{cases}$$

于是有

$$f(x)=\sum_{i=1}^n g_i(x)=\sum_{i=1}^n y_i\prod_{j\neq i}\frac {x-x_j}{x_i-x_j}$$

根据上式可以 $O(n^2)$ 计算出 $f(k)$。

int x[MAXN],y[MAXN];
int Lagrange(int n,int k){
	int ans=0,a,b;
	_rep(i,1,n){
		a=y[i],b=1;
		_rep(j,1,n){
			if(j==i)continue;
			a=1LL*a*(k-x[j])%Mod;
			b=1LL*b*(x[i]-x[j])%Mod;
		}
		ans=(ans+1LL*a*inv(b)%Mod)%Mod;
	}
	return (ans%Mod+Mod)%Mod;
}