over 2 years ago

题目大意

给定,求值:
$$\sum_{k=0}^{n}\binom{n}{k}k^t$$

分析

首先看到我们要有一种把它化成斯特灵数的冲动,一个很常见的转化就是

为什么这样是对的呢?我们考虑就是将个元素放入个不同的空集合中去的方案数,考虑如果放完后有个非空集合,首先代表将个元素分成个非空集合的个数,然后计算选出这个集合的方案数,由于这是排列定义,所以要乘上.
继续刚才的话题,那么原式化成了

把外面的求和提到里面

看到是不是很有感觉,你把它展开就可以得到

那么原式可以化成

也就是

我们可以发现后面的式子就是,因此

现在我们的问题就变成了如何对于一个固定的,快速求出所有.
考虑第二类斯特灵数的组合定义,我们可以知道

为啥是这个式子呢?其实就是容斥原理,设表示把个元素分成个集合且至少有个空集的方案数,,我们考虑把分成个非空集合的方案数就是,就得到了后面那一半,但由于这是排列定义的,而第二类斯特灵数是组合定义的,因此要乘上.
我们继续刚才的话题,有了这个式子后,我们可以将其变形得到

是不是就是一个卷积的式子,因此我们卷积即可,时间复杂度.

← CF260E 又是一道数学题 →
 
comments powered by Disqus