怎么其他神仙都是那么一大堆式子啊……
最近做这种考虑单点贡献的题比较多,考虑单点贡献,发现这个东西和第二类 Stirling 数有关系,对于每个点 $i$,分别考虑加入这个点和不加入这个点,发现贡献为
$$a_i\times (\begin{Bmatrix}
n \\
k
\end{Bmatrix}+(n-1)\times \begin{Bmatrix}
n-1 \\
k
\end{Bmatrix})$$
由第二类 Stirling 数公式
$$\begin{Bmatrix}
n \\
m
\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^{m}(-1)^i\binom{m}{i}(m-i)^n$$
搞一下就出来了。
```cpp
#include<bits/stdc++.h>
#define N 200000
#define reg register
#define inl inline
#define int long long
using namespace std;
const int Mod=1e9+7;
int n,k,sum,a[N+5],fac[N+5],inv[N+5];
inl int Pow(reg int x,reg int y)
{
reg int res=1;
for(;y;y>>=1,x=x*x%Mod) if(y&1) res=res*x%Mod;
return res;
}
inl int Str(reg int x,reg int y)
{
reg int res=0;
for(reg int i=0;i<=y;i++) res=(res+((i&1)?Mod-1:1)*inv[i]%Mod*Pow(y-i,x)%Mod*inv[y-i]%Mod)%Mod;
return res;
}
signed main()
{
scanf("%lld %lld",&n,&k);
for(reg int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum=(sum+a[i])%Mod;
}
fac[0]=1;
for(reg int i=1;i<=n;i++) fac[i]=fac[i-1]*i%Mod;
inv[n]=Pow(fac[n],Mod-2);
for(reg int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%Mod;
reg int ans=sum*(Str(n,k)+(n-1)*Str(n-1,k)%Mod)%Mod;
printf("%lld\n",ans);
return 0;
}
```