CF961G Partitions

Description

有 $n$ 个物品，每个物品有一个权值 $w_i$ 。
现在你需要把这 $n$ 个物品划分成 $k$ 个非空集合。
定义在一个划分下物品的价值为权值和所在集合大小的乘积，一个划分的价值为所有物品的价值之和。

求所有划分的总价值对 $10^9+7$ 取模的值。

$n,k\leq 2\times 10^5$

Solution

首先肯定可以发现答案一定是这个形式

$ans=\sum_{i=1}^{n} A\times w_i$

其中系数 $A$ 与物品无关，只与 $n,k$ 有关。
然后尝试推 $A$ 的表达式。枚举物品最后被分入的集合大小可以得到：

$A=\sum_{i=1}^{n}i\binom{n-1}{i-1}\begin{Bmatrix}n-i\\k-1 \end{Bmatrix}$

模数 $10^9+7$ ，不能直接求第二类斯特林数，必须进一步化简。

像这种又是斯特林数又是组合数的求和式，由于斯特林数展开带幂次项，而组合数和幂次项可以用二项式定理化简，所以展开斯特林数是个不错的选择。

$\begin{aligned} A&=\sum_{i=1}^{n}i\binom{n-1}{i-1}\begin{Bmatrix} n-i\\k-1 \end{Bmatrix}\\ &=\sum_{i=1}^{n}i\binom{n-1}{i-1}\sum_{d=0}^{k-1}\binom{k-1}{d}(-1)^{k-1-d}d^{n-j}\\ &=\frac{(-1)^{k-1}}{(k-1)!}\sum_{d=0}^{k-1}\binom{k-1}{d}(-1)^d\sum_{j=1}^{n}j\times \binom{n-1}{j-1}\times d^{n-j} \end{aligned}$

后面的式子把 $j$ 变成 $(j-1+1)$ 再拆开很明显可以直接用二项式定理化简。可以做到 $\mathcal{O}(k\log_2 n)$ 。

事实上记录这个题是为了一个更加简单的做法：如果将集合大小乘积的贡献，视作是集合其他数对这个数造成的，也就是说视作每一个与 $i$ 同一个集合的数 $j$ 都对 $i$ 有一个 $w_i$ ，那么我们可以得到答案为

$\sum_{i=1}^{n}w_i(\begin{Bmatrix} n \\ k\end{Bmatrix} + (n-1)\begin{Bmatrix} n-1\\k \end{Bmatrix})$

首先 $i$ 对自身的贡献系数为 $\begin{Bmatrix} n \\ k\end{Bmatrix}$ ；将 $i$ 拿去后会有 $\begin{Bmatrix} n-1 \\ k\end{Bmatrix}$ 个划分方法，每一种方法中我们都可以将 $i$ 任意塞入一个集合， 所以系数为 $(n-1)\begin{Bmatrix} n-1 \\ k\end{Bmatrix}$ 。

复杂度也是 $\mathcal{O}(k\log_2 n)$ 。式子应该是恒等的，但是第二种方法更加简捷，计算贡献的方式也是一种挺新颖的方式。

Code

const int N = 2e5 + 5, mod = 1e9 + 7;
using namespace std;
int n, k;
int fac[N], inv[N], invf[N];
int Q(long long b, int t){
    long long ret = 1;
    if(t == - 1) t = mod - 2;
    for(unsigned i = 1;  i <= t; i <<= 1, b = b * b % mod)
        if(i & t) ret = ret * b % mod;
    return ret;
}
int binom(int n, int m){
    if(n < 0 || m < 0 || n - m < 0) return 0;
    return 1ll * fac[n] * invf[m] % mod * invf[n - m] % mod;
}
int main(){

    r(n, k);
    int sum = 0;
    for(int i = 1, x; i <= n; ++i)
        r(x), sum = (sum + x) % mod;
    fac[0] = fac[1] = inv[0] = inv[1] = invf[0] = invf[1] = 1;
    for(int i = 2; i <= 200000; ++i)
        fac[i] = 1ll * i * fac[i - 1] % mod,
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod,
        invf[i] = 1ll * inv[i] * invf[i - 1] % mod;
    int ans = 0;
    for(int d = 0; d < k; ++d){
        int ret = (Q(1 + d, n - 1) + 1ll * (n - 1) * Q(1 + d, n - 2) % mod) % mod;
        ret = 1ll * ret * binom(k - 1, d) % mod;
        if(d & 1) ans = (ans + mod - ret) % mod;
        else ans = (ans + ret) % mod;
    }
    ans = 1ll * ans * invf[k - 1] % mod;
    if(k - 1 & 1) ans = mod - ans;
    w(1ll * ans * sum % mod); 
    return 0;
}