题解 CF961G 【Partitions】
y2823774827y
2019-04-15 10:05:02
## 题目
[CF961G](https://www.luogu.org/problemnew/show/CF961G)
## 前置
斯特林数$\Longrightarrow$[斯特林数及反演总结](https://www.cnblogs.com/y2823774827y/p/10700231.html)
## 做法
相信大家能得出一个一眼式：
$$\displaystyle Ans=\sum\limits_{i=1}^n w_i\sum\limits_{s=1}^n s\cdot C_{n-1}^{s-1}\begin{Bmatrix}k-1\\n-s\end{Bmatrix}$$
然后就开始推式：
$Sum=\displaystyle \sum\limits_{s=1}^n s\cdot C_{n-1}^{s-1}\begin{Bmatrix}k-1\\n-s\end{Bmatrix}$
$~~~~~~~~~=\displaystyle \sum\limits_{s=1}^n s\cdot C_{n-1}^{s-1}\sum\limits_{i=0}^{k-1}\frac{(-1)^i}{i!}\frac{(k-i-1)^{n-s}}{(k-i-1)!}$
$~~~~~~~~~=\displaystyle \sum\limits_{i=0}^{k-1}\frac{(-1)^i}{i!(k-i-1)!}\sum\limits_{s=1}^n s\cdot C_{n-1}^{s-1}(k-i-1)^{n-s}$
$~~~~~~~~~=\displaystyle \sum\limits_{i=0}^{k-1}\frac{(-1)^i}{i!(k-i-1)!}(\sum\limits_{s=1}^nC_{n-1}^{s-1}(k-i-1)^{n-s}+\sum\limits_{s=1}^n (s-1)C_{n-1}^{s-1}(k-i-1)^{n-s})$
$~~~~~~~~~=\displaystyle \sum\limits_{i=0}^{k-1}\frac{(-1)^i}{i!(k-i-1)!}(\sum\limits_{s=1}^nC_{n-1}^{s-1}(k-i-1)^{n-s}+(n-1)\sum\limits_{s=1}^n C_{n-2}^{s-2}(k-i-1)^{n-s})$
$~~~~~~~~~=\displaystyle \sum\limits_{i=0}^{k-1}\frac{(-1)^i}{i!(k-i-1)!}((k-i)^{n-1}+(n-1)(k-i)^{n-2})$
$~~~~~~~~~=\displaystyle \sum\limits_{i=0}^{k-1}\frac{(-1)^i}{i!(k-i-1)!}(k-i)^{n-2}(k-i+n-1)$
然而。。。这。。。比赛的时候能推出这么一大堆式子的**是神仙吧
于是有种更简单的方法：$\displaystyle |S|\sum w_i$
我们可以理解为：划分好集合后，每个点都对当前点有$w_i$的贡献
自己对自己的贡献显然就是$\displaystyle \begin{Bmatrix}n\\k\end{Bmatrix}$
其他点对本身的贡献就是先分好$k$个集合，再放进去，$(n-1)\begin{Bmatrix}n-1\\k\end{Bmatrix}$
$$\displaystyle Ans=\sum\limits_{i=1}^nw_i(\begin{Bmatrix}n\\k\end{Bmatrix}+(n-1)\begin{Bmatrix}n-1\\k\end{Bmatrix})$$
## Code
有关斯特林数及反演的更多姿势$\Longrightarrow$[点这里](https://www.cnblogs.com/y2823774827y/p/10700231.html)
```cpp
#include<cstdio>
typedef int LL;
const LL mod=1e9+7,maxn=2e5+9;
inline LL Read(){
LL x(0),f(1); char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<3)+(x<<1)+c-'0'; c=getchar();
}
return x*f;
}
inline LL Pow(LL base,LL b){
LL ret(1);
while(b){
if(b&1) ret=1ll*ret*base%mod; base=1ll*base*base%mod; b>>=1;
}return ret;
}
LL fav[maxn],fac[maxn];
inline LL Get(LL n,LL m){
LL ret(0);
for(LL i=0;i<=m;++i)
ret=1ll*(ret+1ll*(i&1?mod-1:1)*fav[i]%mod*Pow(m-i,n)%mod*fav[m-i]%mod)%mod;
return ret;
}
LL n,sum,k;
LL w[maxn];
int main(){
n=Read(); k=Read();
for(LL i=1;i<=n;++i){
w[i]=Read();
(sum+=w[i])%=mod;
}
fac[0]=fac[1]=1;
for(LL i=2;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
fav[n]=Pow(fac[n],mod-2);
for(LL i=n;i>=1;--i) fav[i-1]=1ll*fav[i]*i%mod;
printf("%d\n",1ll*sum*((1ll*Get(n,k)%mod+1ll*(n-1)*Get(n-1,k)%mod)%mod)%mod);
return 0;
}
```