Codeforces 961G. Partitions

Solution

给定一个长度为 (n) 的序列 (a_i),你需要把这个序列分成非空的 (m) 组(可以在原数组的基础上打乱),一个组的权值是所有 组内的 (|S|*sum_{i=1}^{|S|}a_i),求所有分法中的所有组的权值和
题面

Solution

考虑每一个点的贡献,每一个点的贡献是一样的,只需要考虑贡献次数就行了
假设正在考虑 (x) 被计算的次数,那么如果有一个 (y) 和它在同一个集合中,就会有 (1) 的贡献(集合长度加 (1))
那么我们把 (x) 单独拿出,只对剩下 (n-1) 进行分组,再把 (x) 拼进 (y) 所在的组,就可以产生贡献 (1) 的了
所以总答案就是 ((S(n,m)+(n-1)*S(n-1,m))*sum_{i=1}^{n} a_i)
第二类斯特林数用展开式算一下就好了

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,mod=1e9+7;
inline int qm(int x,int k){
	int sum=1;
	while(k){
		if(k&1)sum=1ll*sum*x%mod;
		x=1ll*x*x%mod;k>>=1;
	}
	return sum;
}
int inv[N];
inline int S(int n,int m){
	int ret=0,t;
	for(int i=0;i<=m;i++){
		t=1ll*inv[i]*inv[m-i]%mod*qm(m-i,n)%mod;
		if(i&1)ret=(ret-t+mod)%mod;
		else ret=(ret+t)%mod;
	}
	return ret;
}
int main(){
  freopen("pp.in","r",stdin);
  freopen("pp.out","w",stdout);
  int n,m,ans=0,x;
  cin>>n>>m;
  inv[0]=1;for(int i=1;i<=m;i++)inv[i]=1ll*inv[i-1]*qm(i,mod-2)%mod;
  for(int i=1;i<=n;i++)scanf("%d",&x),ans=(ans+x)%mod;
  cout<<1ll*ans*(S(n,m)+1ll*S(n-1,m)*(n-1)%mod)%mod<<endl;
  return 0;
}