给定 $n$ 个坐标 $(x_i,y_i)$，求解唯一确定的最高次不超过 $n-1$ 次的多项式 $f(x)$，满足 $f(x_i)=y_i$。
构造 $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}\tag{1}$$
根据上式可以 $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; }
事实上，如果 $x_i$ 取值连续，上述算法复杂度可以优化为 $O(n)$。
以 $x_i=i$ 为例，则 $(1)$ 式化为
$$f(x)=\sum_{i=1}^n y_i\prod_{j\neq i}\frac {x-j}{i-j}=\sum_{i=1}^n (-1)^{n-i}y_i\frac {\prod_{j=1}^{i-1}(x-j)\prod_{j=i+1}^{n}(x-j)}{(i-1)!(n-i)!}$$
分子部分考虑 $O(n)$ 预处理序列 $\{x-i\}$ 的前缀积和后缀积，分母部分考虑 $O(n)$ 预处理阶乘的逆。
int inv_frac[MAXN],y[MAXN],pre[MAXN],suf[MAXN]; int Lagrange(int x,int n){ pre[0]=suf[n+1]=1; _rep(i,1,n)pre[i]=1LL*pre[i-1]*(x-i)%Mod; for(int i=n;i;i--)suf[i]=1LL*suf[i+1]*(x-i)%Mod; int ans=0,sign; _rep(i,1,n){ sign=((n-i)&1)?-1:1; ans=(ans+1LL*sign*y[i]*pre[i-1]%Mod*suf[i+1]%Mod*inv_frac[i-1]%Mod*inv_frac[n-i])%Mod; } return ans; }
考虑 $O(n)$ 时间动态插入每个点 $(x_i,y_i)$。
令 $g(x)=\prod_{i=1}^n (x-x_i),w_i=\prod_{j\neq i}(x_i-x_j)$，于是 $(1)$ 式化为
$$f(x)=\sum_{i=1}^n y_i\prod_{j\neq i}\frac {x-x_j}{x_i-x_j}=g(x)\sum_{i=1}^n\frac {y_i}{(x-x_i)w_i}\tag{2}$$
于是每次插入后动态更新每个 $w_i$ 即可。
int x[MAXN],y[MAXN],w[MAXN],z; void Insert(int tx,int ty){ w[++z]=1; x[z]=tx,y[z]=ty; _for(i,1,z){ w[i]=1LL*w[i]*(x[i]-x[z])%Mod; w[z]=1LL*w[z]*(x[z]-x[i])%Mod; } } int Lagrange(int k){ int g=1,s=0; _rep(i,1,z){ g=1LL*g*(k-x[i])%Mod; s=(s+1LL*y[i]*inv(1LL*(k-x[i])*w[i]%Mod))%Mod; } return (1LL*g*s%Mod+Mod)%Mod; }
给定一个完全图，完全图中节点编号为 $1\sim n$。$i,j$ 节点间连一条边权为 $(i+j)^k$ 的边。
随机选取 $n-1$ 条边得到一棵生成树，问生成树的边权和的期望值。
发现每条边地位都是等价的，于是每条边出现在生成树的概率为 $\frac{2(n-1)}{n(n-1)}=\frac 2n$。
于是不难得到答案为 $\frac 2n\sum_{i=1}^{n-1}\sum_{j=i+1}^n (i+j)^k$，记 $f(n)=\sum_{i=1}^{n-1}\sum_{j=i+1}^n (i+j)^k$，考虑如何快速求出 $f(n)$。
$$f(n)-f(n-1)=\sum_{i=1}^{n-1}\sum_{j=i+1}^n (i+j)^k-\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1} (i+j)^k=(2n-1)^k+\sum_{i=1}^{n-2}(i+n)=\sum_{i=n+1}^{2n-1}i^k$$
于是有
$$f(n)= \begin{cases} 0, & n=1 \\ \sum_{i=2}^n\sum_{j=i+1}^{2i-1}j^k, & n\gt 1 \end{cases} $$
易知 $\sum_{j=i+1}^{2i-1}j^k$ 是 $k+1$ 次多项式，于是 $\sum_{i=2}^n\sum_{j=i+1}^{2i-1}j^k$ 是 $k+2$ 次多项式。
线性筛预处理 $1^k,2^k\cdots (2k+5)^k$，于是可以线性时间求出 $f(1),f(2)\cdots f(k+3)$，最后套用拉格朗日插值法即可。
总时间复杂度 $O(k)$。