妈妈生的,这个东西在模拟赛里把我干爆了。
记录一些简单的内容,并不会有超纲的多项式。
第二类斯特林数
\(\begin{Bmatrix}n\\ k\end{Bmatrix}\) 表示第二类斯特林数,也可记作 \(S(n,k)\),组合意义是把 \(n\) 个不同元素划分成 \(k\) 个互不区分的子集的方案数。
显然有递推式:
\[S(n,k)=S(n-1,k-1)+k \times S(n-1,k) \]由于它比较简单,是可以直接算出的:
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!} \]直接二项式反演就能证明此公式。
第一类斯特林数
\(\begin{bmatrix}n\\ k\end{bmatrix}\) 表示第一类斯特林数,也可记作 \(s(n,k)\),组合意义是把 \(n\) 个不同元素划分成 \(k\) 个互不区分的环的方案数。
显然有递推式:
\[s(n,k)=s(n-1,k-1)+(n-1) \times s(n-1,k) \]上升幂和普通幂的转化
\[x^{\overline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} x^k \]\[x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} (-1)^{n-k} x^{\overline{k}} \]下降幂和普通幂的转化
事实上这个更加实用,因为组合数就是两个下降幂相除。
\[x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} x^{\underline{k}} \]\[x^{\underline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} (-1)^{n-k} x^k \]于是我们可以将普通多项式转化成下降幂多项式。
在不用任何多项式科技的情况下可以做到 \(\Theta(m^2)\)。
下降幂多项式有很优秀的性质,例如与组合数相乘可以得到漂亮的结果。
标签:begin,end,Bmatrix,斯特林,sum,bmatrix From: https://www.cnblogs.com/tx-lcy/p/18023953