cf961G(第二类斯特林数) | qkoqhh

题目链接

https://codeforces.com/contest/961/problem/G

题意

有 $n$ 个物品，每个物品有权值 $w_i$

定义一个集合 $S$ 的权值为 $W(S)=|S|\sum_{x\in S}w_x$

定义一个划分的权值为 $W’(R)=\sum_{S\subset R}W(S)$

求将 $n$ 个物品划分成 $m$ 个集合的所有方案的权值和

$n,m\le2e5$

题解

直接考虑单点贡献，有

$\begin{aligned} &\sum_{i=1}^{n}w_i\sum_{k=1}^{n-m}(k+1)\binom{n-1}{k}{n-k-1\brace m-1} \\=&\sum w (\sum \binom{n-1}{k}{n-k-1\brace m-1}+\sum k\binom{n-1}{k}{n-k-1\brace m-1}) \end{aligned}$

如果把式中的 $k+1$ 换成 $1$ ，事实上就是在求总方案数了，所以可以得到

$\sum\binom{n-1}{k}{n-k-1\brace m-1}={n\brace m}$

这个式子可以由这个题的场景推导出来，也可以用公式，后面会给出证明

然后代进去

$\begin{aligned} &\sum w ({n\brace m}+\sum k\binom{n-2}{k-1}\frac{n-1}{k}{n-k-1\brace m-1}) \\=&\sum w({n\brace m}+(n-1)\sum \binom{n-2}{k-1} {n-2-(k-1)\brace m-1}) \\=&\sum w({ {n}\brace{m}} +(n-1){n-1\brace m}) \end{aligned}$

然后只要求两个斯特林数就可以了。。这个直接利用 $S_2$ 的卷积公式 $O(m)$ 求就可以了。。呃。。好像有个快速幂，那就 $O(mlogn)$ ，问题不大。。

公式证明

对刚才提到的公式，我们变成一个比较简洁的形式

$\sum_{k=0}^n\binom{n}{k}{m-k\brace m-1}={n+1\brace m}$

感觉就像是先给第一个集合选 $k$ 个数再给后面的集合划分，然后答案是 $n\brace m$ ？其实不然，这样做会有一个问题就是会把第一个集合和其他集合形成相对顺序，然后会导致重复计数

这个可以用 $S_2$ 的卷积展开来推导

$\begin{aligned} \sum_{k=0}^n\binom{n}{k}{m-k\brace m-1}&=\sum_{k=0}^n\binom{n}{k} \sum_{j=0}^{m-1}\frac{(-1)^j}{j!}\frac{(m-1-j)^{n-k}}{(m-1-j)!} \\&=\sum_{j=0}^{m-1}\frac{(-1)^j}{j!(m-1-j)!}\sum_{k=0}^n\binom{n}{k}(m-1-j)^{n-k} \\&=\sum_{j=0}^{m-1}\frac{(-1)^j}{j!(m-1-j)!}(m-j)^n \\&=\sum_{j=0}^{m-1}\frac{(-1)^j}{j!}\frac{(m-j)^{n+1}}{(m-j)!} \\&={n+1\brace m} \end{aligned}$

代码

/**
 *　　　　　　  　　┏┓　　 　┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　┃ 　
 * 　　　　　  　　┃　　　━　　 　┃
 * 　　　　　  　　┃　＞　　　＜　┃
 * 　　　　　  　　┃　　　　　　　┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */ 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<cstdlib>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define mid (x+y>>1)
#define sqr(x) ((x)*(x))
#define NM 200005
#define nm 400005
const double pi=acos(-1);
const ll inf=1e9+7;
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}
 




int n,m;
ll ans,s,p[NM],inv[NM],invp[NM];

ll qpow(ll x,ll t){
    ll s=1;
    for(;t;t>>=1,x=sqr(x)%inf)if(t&1)s=s*x%inf;
    return s;
}


int main(){
    n=read();m=read();
    inc(i,1,n)ans+=read(),ans%=inf;
    p[0]=p[1]=invp[1]=invp[0]=inv[1]=1;
    inc(i,2,m)inv[i]=inv[inf%i]*(inf-inf/i)%inf,invp[i]=invp[i-1]*inv[i]%inf,p[i]=p[i-1]*i%inf;
    inc(k,0,m){
	ll t=qpow(m-k,n-1);
	if(k&1)s+=inf-invp[k]*invp[m-k]%inf*t%inf*(m-k)%inf,s%=inf;
	else s+=invp[k]*invp[m-k]%inf*t%inf*(m-k)%inf,s%=inf;
	if(k&1)s+=inf-invp[k]*invp[m-k]%inf*t%inf*(n-1)%inf,s%=inf;
	else s+=invp[k]*invp[m-k]%inf*t%inf*(n-1)%inf,s%=inf;
    }
    return 0*printf("%lld\n",ans*s%inf);
}