第二类斯特林数题乱做

被二斯整怕了/kk 下面 $S$ 表示第二类斯特林数 ### CF932E Team Work 题意： 求 $$\sum_{i=1}^n\binom{n}{i}i^k$$ $$=\sum_{i=0}^n\binom{n}{i}i^k$$ 这个变化后面特判就好了 $$=\sum_{i=0}^n\binom{n}{i}\sum_{j=0}^iS(k,j)\times \frac{i!}{(i-j)!}$$ $$=\sum_{i=0}^n \frac{n!}{(n-i)!}\sum_{j=0}^iS(k,j)\times \frac{1}{(i-j)!}$$ 交换求和顺序 $$ =\sum_{j=0}^k S(k,j)\sum_{i=j}^{n} \frac{n!}{(i-j)!(n-i)!} $$ 令$i=i-j$ $$ =\sum_{j=0}^k S(k,j)\sum_{i=0}^{n-j}\frac{n!}{i!(n-i-j)!} $$ $$ =\sum_{j=0}^k S(k,j)\sum_{i=0}^{n-j}\frac{n!}{i!(n-i-j)!}\times \frac{(n-j)!}{(n-j)!} $$ $$ =\sum_{j=0}^k S(k,j)\sum_{i=0}^{n-j}\frac{(n-j)!}{i!(n-i-j)!}\times \frac{n!}{(n-j)!} $$ $$ =\sum_{j=0}^k S(k,j)\frac{n!}{(n-j)!}\sum_{i=0}^{n-j}\binom{n-j}{i} $$ $$ =\sum_{j=0}^k S(k,j)\frac{n!}{(n-j)!}2^{n-j} $$ $O(k^2)$ ### 洛谷2791 幼儿园篮球题 前置知识：范德蒙恒等式： $$\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}$$ 相当于 $n+m$ 个物品中选 $k$ 个嘛 题目要我们求的是 $$ \frac{\sum_{i=0}^k \binom{m}{i}\binom{n-m}{k-i}i^L}{\binom{n}{k}} $$ 只考虑分子，把 $i^L$ 干掉 $$ \sum_{i=0}^k \binom{m}{i}\binom{n-m}{k-i}\sum_{j=0}^iS(L,j)\binom{i}{j}j! $$ $$ =\sum_{j=0}^LS(L,j)j!\sum_{i=j}^k \binom{m}{i}\binom{n-m}{k-i}\binom{i}{j} $$ 注意$\binom{m}{i}\times\binom{i}{j}=\binom{m-j}{i-j}\binom{m}{j}$ $$ =\sum_{j=0}^LS(L,j)\binom{m}{j}j!\sum_{i=j}^k \binom{n-m}{k-i}\binom{m-j}{i-j} $$ 发现后面的和式中，上面没有 $i$ ，下面的和也没有 $i$，所以直接上范德蒙恒等式。 $$ =\sum_{j=0}^LS(L,j)\binom{m}{j}j!\sum_{i=j}^k \binom{n-j}{k-j} $$ 于是 $O(n\log n)$ 预处理出二斯后单次询问就是 $O(L)$ 了。 不过有一些边界，注意下就好了。 ### 洛谷4827 Crash 的文明世界 考察了一个简单转换，但我连这都不会/kk 对于树上每个位置$x$ $$ S=\sum_{i=1}^n \operatorname{dist(i,x)^k} $$ $$ =\sum_{i=1}^n \sum_{j=0}^k S(k,j)j! \binom{\operatorname{dist(i,x)}}{j} $$ $$ =\sum_{i=1}^n \sum_{j=0}^k S(k,j)j! \binom{\operatorname{dist(i,x)}-1}{j-1}+\binom{\operatorname{dist(i,x)}-1}{j} $$ 然后就发现记$f_{x,j}$为$x$子树内$\sum\binom{\operatorname{dist(i,x)}}{j}$的值即可，计算儿子对父亲的贡献就是$f_{x,j}+=f_{v,j-1}+f_{j,j}$，然后换根DP即可。