CF961G Partitions

给出 $n$ 个物品，每个物品有一个权值 $w_i$。
定义一个集合 $S$ 的权值为 $W(S)=|S|\sum_{x\in S} w_x$，对于一个集合的划分，定义其权值为 $W'(R)=\sum_{S\in R} W(S)$。
求所有将 $n$ 个物品分为 $k$ 个集合的方案的权值和。
$n,k \le 2\times 10^5,w_i \le 10^9$

$\texttt{Solution}$

考虑一个物品 $i$ 对答案的贡献，不难发现其贡献为：

$$w_i \times \sum |S|$$

$|S|$ 是每次 $i$ 所在集合的大小。

可以把 $i$ 这个物品单独拎出来，对剩下 $n-1$ 个物品划分集合，然后把 $i$ 加入其中某个集合。首先，如果 $i$ 单独做一个集合，那么 $|S|$ 为 $1$，其他的物品划分方案数为 $\begin{Bmatrix} n - 1\\ k - 1 \end{Bmatrix}$。否则，$i$ 不是单独成一个集合，先将 $n-1$ 个数字划分成 $k$ 个集合，方案数为：$\begin{Bmatrix} n - 1\\ k \end{Bmatrix}$，然后考虑将 $i$ 放入哪个集合，若原本该集合大小为 $v$ ，那么加入 $i$ 后大小为 $v+1$。发现某一个集合的大小并不好求，但是不难发现集合的总大小为 $n+k-1$，也就是把每个集合原本的大小加起来，再加上 $k$ 个 $1$。因此若 $i$ 不单独成集合，对答案的贡献的方案数为 $(n+k-1)\begin{Bmatrix} n - 1\\ k \end{Bmatrix}$。

因此一个 $i$，对答案的贡献是：

$$w_i \times \Big(\begin{Bmatrix} n - 1\\ k - 1 \end{Bmatrix}+(n+k-1)\begin{Bmatrix} n - 1\\ k \end{Bmatrix}\Big)$$

容易发现后面的柿子和 $i$ 完全无关，因此可以把每一个位置的答案一起求。我们令 $W=\sum_{i=1}^n w_i$，那么答案是：

$$W \times \Big(\begin{Bmatrix} n - 1\\ k - 1 \end{Bmatrix}+(n+k-1)\begin{Bmatrix} n - 1\\ k \end{Bmatrix}\Big)$$

但是第二类斯特林数不能 $\mathcal{O}(n^2)$ 递推，因此考虑使用通项公式。

有：

$$\begin{Bmatrix} n\\ k \end{Bmatrix}=\dfrac{1}{k!}\sum_{i=0}^k \binom{k}{i} (-1)^{i} (k-i)^n$$

可以通过二项式反演证明：

$$x^n=\sum_{k=0}^n \begin{Bmatrix} n\\ k \end{Bmatrix} x^{\underline{k}}=\sum_{k=0}^n \begin{Bmatrix} n\\ k \end{Bmatrix} \binom{x}{k} k!$$

二项式反演即可得到之前的柿子。

然后直接 $\mathcal{O}(n)$ 求单点斯特林数即可。

标签: 数学, 斯特林数, 二项式反演

添加新评论