第二类斯特林数
定义： \( \begin{Bmatrix} n\\ m\end{Bmatrix} \) 为 \(n\) 个数划分成 \(m\) 个集合的方案数。
递归式： \( \begin{Bmatrix} n\\ m\end{Bmatrix}= \begin{Bmatrix} n-1\\ m-1\end{Bmatrix}+m \begin{Bmatrix} n-1\\ m\end{Bmatrix} \) [根据组合意义理解]
常用式： \(x^{k}=\sum_{i=1}^{k}\begin{Bmatrix} k\\ i \end{Bmatrix}\binom{x}{i} i!\)
拉格朗日插值
应用： 对于一个多项式，我们可以 \(n^2\) 求出对应值 （ \(n\) 为项数 ）
公式：
[正确性显然]
拉格朗日插值求多项式系数
对于上面的公式，我们先把常数提出
令：
得：
\[f(x)=\sum_{i=1}^{n}g(i)\prod_{j=1,i\neq j}^{n}{x-x_j} \]然后我们就可以模拟多形式乘，多项式除来得到系数
Code
inline void sleve() {
for(re int x=1;x<=k+2;x++) {
xx[x]=x;
yy[x]=(yy[x-1]+qpow(x,k))%mol;
}
}
inline int inv(int a) { return qpow(a,mol-2); }
inline void wor() {
sleve();
for(re int i=1;i<=k+2;i++) {
c[i]=1;
for(re int j=1;j<=k+2;j++) if(i!=j) (c[i]*=(xx[i]-xx[j]+mol)%mol)%=mol;
c[i]=inv(c[i])*yy[i]%mol;
}
fs[0]=1;
for(re int i=1;i<=k+2;i++) {
for(re int j=k+1;j>=1;j--) fs[j]=(fs[j-1]+fs[j]*(mol-xx[i])%mol)%mol;
(fs[0]*=(mol-xx[i]))%=mol;
}
for(re int i=1;i<=k+2;i++) {
int ls=inv(mol-xx[i]);
g[0]=fs[0]*ls%mol;
for(re int j=1;j<=k+1;j++) g[j]=(fs[j]-g[j-1]+mol)%mol*ls%mol;
for(re int j=0;j<=k+1;j++) (f[j]+=g[j]*c[i]%mol)%=mol;
}
}
珂朵莉树
应用： 对于随机数据的有效优化，适用于统一大范围修改
（这里填了一个大坑）
我们可以快速算出区间覆盖问题，
一开始可以把 \(1～n\) 全插进 \(set\) 里，权值为0,
每插进一段区间，就把对应区间的权值改为1,最后询问区间和即可。