讲递推和初步性质。退役前可能学不到多项式。
第一类斯特林数：$s(n,m) $把 \(n\) 个元素分成 \(m\) 组圆排列的方案，圆排列是 \((n-1)!\)。
从 dp 意义上推递推公式，设 \(s(i,j)=dp_{i,j}\) 为 \(i\) 个元素分 \(j\) 组圆排列的方案。则第 \(i\) 个元素可以独立成组或者加入到先前组的某个元素旁边，有转移
\[s(i,j)=s(i-1,j-1)+(i-1)*s(i-1,j) \]初始化 \(s(0,0)=s(1,1)=1,s(i,1)=(i-1)!\)
这个东西还可以用来推上升幂下降幂相关，是多项式的内容，提一嘴。
\[x^{\overline n}=x(x+1)(x+2)...(x+n-1)=\sum_{i=1}^ns_u(n,i)x^i \\ x^{\underline n}=x(x-1)(x-2)...(x-n+1)=\sum_{i=1}^ns_s(n,i)x^i \]其中 \(s_u()\) 就是 \(s()\)，\(s_s(n,m)=(-1)^{n+m}s_u(n,m)\)
排个序从中抽若干个点 \(p_i,p_i>p_{i-1}\) 作为能看到的贡献点那剩下的那部分点可以围在这些 \(p_i\) 周围，\(n\) 会把答案分成 \(A-1+B-1\) 组，那就相当于用 \(n-1\) 个元素形成了 \(A+B-2\) 组环排列。答案即 \(\begin{bmatrix}n-1\\A+B-2\end{bmatrix}\binom{A+B-2}{A-1}\)
第二类斯特林数：\(S(n,m)\) 把 \(n\) 个不同的球放到 \(m\) 个相同盒子里的方案，求法是类似的，第 \(i\) 个球要么独立成盒要么放到先前某个盒子里。
\[S(i,j)=S(i-1,j-1)+j*S(i-1,j) \]然后捯饬一下可以解决一些小问题比如 \(n\) 个不同球放 \(m\) 个不同盒就考虑盒自排列即 \(m!S(n,m)\)。\(n\) 个球放到 \(m\) 个可以为空的盒子就是 \(\sum_{i=1}^mS(n,i)\)。
然后 \(n\) 个不同球放到 \(m\) 个可以为空的不同盒显然是 \(n^m\)，用斯特林数表示可以是 \(\sum_{i=1}^mi!\binom{m}{i}S(n,i)\)。
然后这个就是斯特林展开即
\[x^k=\sum_{i=0}^k\begin{Bmatrix}n\\i\end{Bmatrix}i!\binom{k}{i} \]模拟赛考的是树上全点对路径长 \(k\) 次方和，二项式定理展开维护一下 \(i\) 次方贡献跑点分治能过 \(10^5\)，但是淀粉质感觉不太能做这题。这个题直接把换根 \(dp\) 写脸上了。
\[\begin{align*} Ans&=\sum_{x=1}^n\sum_{y=1}^n\sum_{i=0}^k\begin{Bmatrix} k\\ i \end {Bmatrix}*i!*\binom{dis(x,y)}{i} \\ &=\sum_{i=0}^k\begin{Bmatrix} k\\ i \end {Bmatrix}*\sum_{x=1}^n\sum_{y=1}^ni!*\binom{dis(x,y)}{i} \end{align*} \]然后 \(i!*\binom{dis(x,y)}{i}\) 可以写成一个下降幂的形式并且下降幂有性质 \((x+1)^ {\underline i}=ix^{\underline {i-1}}+x^{\underline i}\)。那就可以维护 \(f_{u,i},dp_{u,i}\) 表示 \(u\) 子树到 \(u\) 和 \(u\) 它爹的 \(i\) 次下降幂和有转移
\[f_{u,i}=\sum_{v\in son_u}dp_{v,i}\\ dp_{u,i}=if_{u,i-1}+f_i \]然后换个根就是 \(u->v\) 则 \(u\) 刨去 \(v\) 子树部分的距离要 \(+1\)，剩下的不变，给每次 \(f_{v,i}\) 提供一个修正量
\[V_i=f_{u,i}-dp_{v,i}\\ f_{v,i}+=iV_{i-1}+V_i \]统计一下就好了。
标签：end,斯特林,sum,Bmatrix,binom,dp From： https://www.cnblogs.com/Claimo0611/p/18533725