题目链接
(Solution)
首先,这个直接推式子。自己推去
所以我们来想一想一些巧妙的方法
(|S|sum w_i) 可以转化为:划分好集合后,每个点都对当前点有(w_i)的贡献
那么我们只要枚举每一个数(j)对(i)的贡献即可
当(i=j)时 贡献为:$$egin{Bmatrix} n k end {Bmatrix}$$
当(i eq j)时 贡献为:$$egin{Bmatrix} n-1 k end {Bmatrix}$$
所以总贡献为:
[egin{Bmatrix} n \ k end {Bmatrix}+egin{Bmatrix} n-1 \ k end {Bmatrix}
]
斯特林数用这个算:
[egin{Bmatrix} n \ m end {Bmatrix}=frac{1}{m!}sum_{i=0}^{m}(-1)^iinom m i(m-i)^n
]
(Code)
#include<bits/stdc++.h>
#define int long long
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
const int mod=1e9+7;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return f*x;
}
int ksm(int a,int b){
int ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod,b>>=1;
}
return ans;
}
int jc[1000001];
int S(int x,int y){
int ans=0;
for(int i=0;i<=y;i++)
ans=(ans+(i&1?mod-1:1)*jc[y]%mod*ksm(jc[i],mod-2)%mod*ksm(jc[y-i],mod-2)%mod*ksm(y-i,x)%mod)%mod;
return ans*ksm(jc[y],mod-2)%mod;
}
main(){
int n=read(),k=read(),ans=0;
jc[0]=1;
for(int i=1;i<=n;i++)
ans=(ans+read())%mod,jc[i]=jc[i-1]*i%mod;
printf("%lld",(ans*(S(n,k)+S(n-1,k)*(n-1)%mod)%mod)%mod);
return 0;
}