CF961G Partitions

题面

简化题意

给定 $n$ 个物品，每个物品有权值 $w_i$，定义一个集合 $S$ 的权值为 $W(S) = \left|S\right| \sum_{x\in S} w_x$。

定义一个划分的权值为其划分出的所有集合权值的和。

求把 $n$ 个物品划分为 $k$ 个集合的所有方案的权值和，对 $10^9+7$ 取模。

$n\leq 2\times 10^5$。

题解

组合意义天地灭

考虑计算集合贡献时 $\left|S\right|$ 表示啥，其实就是每个物品会对系数产生 $1$ 的贡献。而划分好集合后，每个点都对当前点有 $w_i$ 的贡献。

钦定一个点，则每个点对自己的贡献是 $n\brace m$，而一个点对其他点的贡献是：把其他点划分好集合，则这个点对 $i$ 的贡献是把自己和 $i$ 放在一个集合里，也就是 $n-1 \brace k$。因此：

$ans = \left[{n\brace k} + (n-1){n-1 \brace k}\right] \sum w_i$

复杂度 $n\log n$。

namespace sol1{
    inline int S(int n,int m){
        int res=0;
        for(register int i=0;i<=m;++i){
            res+=C(m,i)*mi(m-i,n)%mod*(i&1?-1:1),
            res=(res+mod)%mod;
        }
        return res*inv[m]%mod;
    }
    inline void sol(){
        write((S(n,k)+(n-1)*S(n-1,k)%mod)%mod*sumw%mod);
    }
}

代数推导保平安

不妨枚举每一个点，枚举这个点所在的集合大小。

则这个点产生的贡献为：自己的 $w_i$ 乘上分配集合的方案数。

$ans = \sum w_i \sum_{j=1}^n {n-j \brace k-1}\binom{n-1}{j-1} j$

其中第二个 $\sum$ 为：除开这个集合，剩下的物品分配方案数乘上除开枚举的这个点，剩下的点放进这个集合的方案数。贡献还需要乘上集合大小。

然后拆斯特林数：

$\sum w_i \sum_{j=1}^n \binom{n-1}{j-1} \frac{j}{(k-1)!} \sum_{p=0}^{k-1} (-1)^p \binom{k-1}{p} (k-i-p)^j$

交换 $\sum$：

$\sum w_i \sum_{p=0}^{k-1} (-1)^p\binom{k-1}{p} \frac{1}{(k-1)!} \sum_{j=1}^n j \binom{n-1}{j-1} (k-1-p)^{n-j}$

只考虑后面的 $\sum$。后面这里乘上了一个 $j$，非常麻烦，如果不乘的话就可以二项式定理往上套了。但是考虑到组合数里面有个 $j-1$，于是把 $j$ 变成 $j+1-1$，后面的部分变成：

$\sum_{j=1}^n (j-1)\binom{n-1}{j-1}(k-1-p)^{n-j} + \sum_{j=1}^n \binom{n-1}{j-1} (k-1-p)^{n-j}$

第一项拆开，发现可以凑成另一个组合数，第二项二项式定理：

$(n-1)\sum_{j=1}^n \binom{n-2}{j-2}(k-1-p)^{n-j} + (k-p)^{n-j}$

然后你发现第一项也可以二项式定理了：

$(n-1)(k-p)^{n-2} + (k-p)^{n-1}$

代回答案：

$ans = \sum w_i \sum_{p=0}^{k-1}(-1)^p \frac{(n-1)(k-p)^{n-2}+(k-p)^{n-1}}{p!(k-1-p)!}$

复杂度 $n\log n$。

namespace sol2{
    inline void sol(){
        int ans=0;
        if(n==1){
            write(sumw);
            return;
        }
        for(register int p=0;p<k;++p){
            int fz=((n-1)*mi(k-p,n-2)%mod+mi(k-p,n-1))%mod;
            int fm=inv[p]*inv[k-1-p]%mod;
            ans+=fz*fm%mod*(p&1?-1:1),
            ans=(ans+mod)%mod;
        }
        write(ans*sumw%mod);
    }
}