前言
技不如人，甘拜下风
这题神仙推式，顶不住顶不住
输了
前置芝士——一些组合数的公式
[kleft(egin{matrix}n\kend{matrix}
ight)=left(egin{matrix}n-1\k-1end{matrix}
ight)n
]
[sum_{i=0}^nleft(egin{matrix}n\iend{matrix}
ight)(k-1)^{n-i}=k^n
]
二项式定理可证（左边乘上(1^i)）
思路
求和式
单独考虑每个数x出现的次数，即每个物体对总答案的贡献肯定是(w_i imes p_i)，(p_i)是一个系数，现在考虑如何求出这个系数
考虑对于一个大小为k的集合，如果物体在其中，则有(left(egin{matrix}n-1\k-1end{matrix}
ight))种方式可以选到它，剩下的数再组成k-1个集合，就是第二类斯特林数(left{ egin{matrix}n-k\k-1end{matrix}
ight})
所以可以枚举集合大小，答案就是
[sum_{i=1}^nw_isum_{j=1}^njleft(egin{matrix}n-1\j-1end{matrix}
ight)left{ egin{matrix}n-k\k-1end{matrix}
ight}
]
颓式子
我们要求的式子长这样
[sum_{i=1}^nw_isum_{j=1}^njleft(egin{matrix}n-1\j-1end{matrix}
ight)left{ egin{matrix}n-k\k-1end{matrix}
ight}
]
先发现(sum_{i=1}^nw_i)这一项和后面毫无关联，把它去掉只考虑后面的式子
对于(sum_{j=1}^njleft(egin{matrix}n-1\j-1end{matrix}
ight)left{ egin{matrix}n-k\k-1end{matrix}
ight})，带入第二类斯特林数的通式
得到
[egin{align}&sum_{j=1}^njleft(egin{matrix}n-1\j-1end{matrix}
ight)sum_{t=0}^{k-1}frac{(-1)^t}{t!}frac{(k-1-t)^{n-j}}{(k-1-t)!}\
=&sum_{t=0}^{k-1}frac{(-1)^t}{t!(k-t-1)!}sum_{j=1}^njleft(egin{matrix}n-1\j-1end{matrix}
ight)(k-1-t)^{n-j}end{align}
]
发现后面部分只和j有关，单独考虑后面的部分
[egin{align}&sum_{j=1}^njleft(egin{matrix}n-1\j-1end{matrix}
ight)(k-1-t)^{n-j}\
=&sum_{j=1}^nleft(egin{matrix}n-1\j-1end{matrix}
ight)(k-1-t)^{n-j}+sum_{j=1}^n(j-1)left(egin{matrix}n-1\j-1end{matrix}
ight)(k-1-t)^{n-j}\
=&sum_{j=1}^nleft(egin{matrix}n-1\j-1end{matrix}
ight)(k-1-t)^{n-j}+(n-1)sum_{j=1}^nleft(egin{matrix}n-2\j-2end{matrix}
ight)(k-1-t)^{n-j}\
=&(k-t)^{n-1}+(n-1)(k-t)^{n-2}\
=&(k-t)^{n-2}(n-1+k-t)end{align}
]
带入回去，得到
[ans=sum_{t=0}^{k-1}frac{(-1)^t}{t!(k-1-t)!}(k-t)^{n-2}(n+k-t-1)
]
然后就可以(O(klog k))的快速求解了
真实理性愉悦
不是很长的代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int MOD = 1000000007;
int pow(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[200100],inv[200100];
void init(int n){
jc[0]=inv[0]=1;
for(int i=1;i<=n;i++){
jc[i]=jc[i-1]*i%MOD;
inv[i]=pow(jc[i],MOD-2);
}
}
signed main(){
int n,k,sum=0,el=0;
scanf("%lld %lld",&n,&k);
for(int i=1;i<=n;i++){
int mid;
scanf("%lld",&mid);
sum=(sum%MOD+mid%MOD)%MOD;
}
if(n==1&&k==1){
printf("%d
",sum);
return 0;
}
else if(n==1){
printf("0
");
return 0;
}
init(k);
for(int t=0;t<=k-1;t++){
el=(el+(((t&1)?-1:1)+MOD)%MOD*inv[t]%MOD*inv[k-t-1]%MOD*pow(k-t,n-2)%MOD*(n+k-t-1)%MOD)%MOD;
}
printf("%lld
",sum*el%MOD);
return 0;
}
[]