【题解】CF961G Partitions

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)$ 求单点斯特林数即可。

添加新评论