C++(g++ 7.5.0) 解法, 执行用时: 81ms, 内存消耗: 4356K, 提交时间: 2022-10-12 23:21:13

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn = 2e5 + 10;
constexpr int P = 1e9 + 7;

ll fac[maxn], ifac[maxn];

ll qpow(int x, int k = P-2){
	int ans = 1;
	while(k){
		if(k&1) ans = 1ll * ans * x % P;
		x = 1ll * x * x % P, k >>= 1;
	}
	return ans;
}

void solve(){
	int n,k; cin >> n >> k;
	vector<int>a(n);
	for(int i = 0 ; i < n ; i ++) cin >> a[i];

	fac[0] = 1;
	for(int i = 1 ; i <= n ; i ++) fac[i] = fac[i-1] * i % P;
	ifac[n] = qpow(fac[n]);
    for(int i = n ; i >= 1 ; i --) ifac[i-1] = ifac[i] * i % P;

    auto C = [&](int n, int m){
    	return fac[n] * ifac[m] % P * ifac[n-m] % P;
    };

    auto F = [&](int n, int k)->ll{
    	ll ans = 0;
    	for(int i = 0 ; i <= k ; i ++){
    		int flag = (i&1?-1:1);
    		ans = (ans + flag * C(k,i) * qpow(k-i,n)) % P;
    	}
    	ans = (ans%P+P)%P;
    	return ans * ifac[k] % P;
    };

    ll s1 = accumulate(a.begin(), a.end(), 0ll) % P;
    ll s2 = (F(n,k)+(n-1)*F(n-1,k)) % P;

    cout << s1 * s2 % P;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

    solve();

	return 0;
}

C++ 解法, 执行用时: 34ms, 内存消耗: 2060K, 提交时间: 2022-03-11 19:17:53

#include<bits/stdc++.h>
using namespace std;
const int P = 1e9+7;
const int N = 2e5+10;

int qpow(int x,int q){
	if(q<=0) return 1; 
	int res=1;
	while(q){
		if(q&1) res=1ll*res*x%P;
		x=1ll*x*x%P,q>>=1;
	}
	return res;
} 

int fac[N],ifac[N];
void fac_init(int t){
	fac[0]=fac[1]=1;
	for(int i=2;i<=t;++i)  fac[i]=1ll*fac[i-1]*i%P;
	ifac[t]=qpow(fac[t],P-2);
	for(int i=t-1;i>=0;--i) ifac[i]=1ll*(i+1)*ifac[i+1]%P;
}

inline int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int main()
{
	int n=read(),k=read(),sum=0,res=0;
	fac_init(k);
	for(int i=1,x;i<=n;++i) x=read(),sum=(1ll*x+sum)%P;
	for(int i=0,f=1;i<k;++i,f=P-f) res=(1ll*f*ifac[i]%P*ifac[k-1-i]%P*(k+n-i-1)%P*qpow(k-i,n-2)%P+res)%P;
	printf("%lld",1ll*res*sum%P);
}