CodeForces

分析

可以发现每种权值的贡献是一样的，我们只要求出这个系数就好了。

注意到贡献的式子里有一个 $|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;
}