分析
可以发现每种权值的贡献是一样的,我们只要求出这个系数就好了。
注意到贡献的式子里有一个 $|S|$ 。我们可以认为集合中的每个元素对答案都有一次贡献。
于是枚举每一对数的贡献即可。
$i$ 对自身的贡献显然为 $S_n^k$ 。
当 $j\neq i$ 时,贡献为 $S_{n-1}^k$ 。
于是总的系数就是 $S_n^k+(n-1)\times S_{n-1}^k$ 。
代码
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=200000+10;
const int mod=1000000007;
int n,k;
int w[N];
int fac[N],inv[N];
inline int fastpow(int a,int b) {
int ans=1;
for (;b;b>>=1,a=1ll*a*a%mod)
if (b&1) ans=1ll*ans*a%mod;
return ans;
}
inline int S(int n,int m) {
int ans=0;
for (re int i=0,j=1;i<=m;++i,j=-j) {
int tmp=1ll*j*fastpow(m-i,n)*inv[i]%mod*inv[m-i]%mod;
ans=(ans+tmp)%mod;
}
return (ans+mod)%mod;
}
int main() {
n=read(),k=read();
for (re int i=1;i<=n;++i) w[i]=read();
fac[0]=1;
for (re int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=fastpow(fac[n],mod-2);
for (re int i=n;i;--i) inv[i-1]=1ll*inv[i]*i%mod;
int ans=0;
for (re int i=1;i<=n;++i) ans=(ans+w[i])%mod;
ans=1ll*ans*(S(n,k)+1ll*(n-1)*S(n-1,k)%mod)%mod;
printf("%d\n",ans);
return 0;
}
2 条评论
那个(n-1)是啥qwq
有 $n-1$ 个 $j\neq i$ 啊qwq