CF961G Partitions

· · 个人记录

我又想着DP了。。菜

首先认识到每个人本质相同，于是想到计算贡献。即求每个人的权值会被贡献多少次。

其次发现这个每个物品划分入集合就是球盒问题，而且本题中物品本质不同集合本质相同，不能为空，就是第二类斯特林数干的事！

因为贡献中有个集合大小|S|，自然想到先枚举它

所以能写出这样的柿子：

\choose s-1}S_{n-s,k-1}

只考虑第二个sigma那个系数；

而斯特林数有这个公式：S_{n,m}=\frac{1}{m!}\sum_{i=0}^m(-1)^i{m\choose i}(m-i)^n

（虽然知道这个是二项式反演的结果，但好像还是直接理解比较好：枚举几个盒子一定为空。除以阶乘就是盒子无标号的结果）

终于见到用这个柿子的推柿子题啦！

\choose s-1}S_{n-s,k-1} \choose s-1}s\frac{1}{(k-1)!}\sum_{i=0}^{k-1}(-1)^i{k-1\choose i}(k-1-i)^{n-s}

然后套路地交换求和符号，拆开组合数，改变枚举量的范围，得到了这个柿子：

=\sum_{i=0}^{k-1}\frac{(-1)^i}{i!(k-i-1)!}\sum_{s=0}^{n-1}(s+1){n-1\choose s}(k-i-1)^{n-1-s}

下面是没见过的操作：

注意到第二个simga的柿子很接近可以二项式定理的形式，但是多了个(s+1)。我们把这个括号拆开：

=\sum_{i=0}^{k-1}\frac{(-1)^i}{i!(k-i-1)!}\bigg(\sum_{s=0}^{n-1}s{n-1\choose s}(k-i-1)^{n-1-s}+\sum_{s=0}^{n-1}{n-1\choose s}(k-i-1)^{n-1-s}\bigg)

括号里第二个可以直接二项式定理：

=\sum_{i=0}^{k-1}\frac{(-1)^i}{i!(k-i-1)!}\bigg(\sum_{s=0}^{n-1}s{n-1\choose s}(k-i-1)^{n-1-s}+(k-i)^{n-1}\bigg)

左边的sigma，我们有一个恒等式：k{n\choose k}=\frac{kn!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}=n\frac{(n-1)!}{(k-1)!(n-k)!}=n{n-1\choose k-1}

一看就知道这个柿子正好能用上——n提到外面，里面就可以二项式定理了：

=\sum_{i=0}^{k-1}\frac{(-1)^i}{i!(k-i-1)!}\bigg(n\sum_{s=0}^{n-1}{n-2\choose s-1}(k-i-1)^{n-1-s}+(k-i)^{n-1}\bigg) =\sum_{i=0}^{k-1}\frac{(-1)^i}{i!(k-i-1)!}\bigg(n\sum_{s=0}^{n-2}{n-2\choose s}(k-i-1)^{n-2-s}+(k-i)^{n-1}\bigg) =\sum_{i=0}^{k-1}\frac{(-1)^i}{i!(k-i-1)!}\bigg(n(k-i)^{n-2}+(k-i)^{n-1}\bigg)

推完了，直接算就行了。

这个题学到的：

另一个方法更加巧妙：

对着柿子构造组合意义：

主要难在乘上所在集合大小这个东西。

看做它对自己所在集合里的每个元素都做一次w_i的贡献。

于是就可以对于每对<i,j>，考虑i对j的贡献即可！

当j==i时，方案数多少？就是斯特林数S_{n,k}

当j!=i时，相当于要求j和i在一个集合里，方案数多少？直接把它们俩绑起来看做一个物品！为S_{n-1,k}。

注意到j!=i时，所有的j本质相同。

所以每个w_i要乘的系数是{S_{n,k}+(n-1)S_{n,k-1}}

这和上面推的柿子是相同的。

（j!=i有点口胡的成分，感觉是对的。。。？）