「CF 961G」Partitions

题目链接

戳我

\(Solution\)

首先，这个直接推式子。自己推去

所以我们来想一想一些巧妙的方法

\(|S|\sum w_i\) 可以转化为：划分好集合后，每个点都对当前点有\(w_i\)的贡献

那么我们只要枚举每一个数\(j\)对\(i\)的贡献即可

当\(i=j\)时 贡献为:$$\begin{Bmatrix} n \ k \end {Bmatrix}$$

当\(i \neq j\)时 贡献为:$$\begin{Bmatrix} n-1 \ k \end {Bmatrix}$$

所以总贡献为:

\[\begin{Bmatrix} n \\ k \end {Bmatrix}+\begin{Bmatrix} n-1 \\ k \end {Bmatrix}
\]

斯特林数用这个算:

\[\begin{Bmatrix} n \\ m \end {Bmatrix}=\frac{1}{m!}\sum_{i=0}^{m}(-1)^i\binom m i(m-i)^n
\]

\(Code\)

#include<bits/stdc++.h>

#define int long long

#define rg register

#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

using namespace std;

const int mod=1e9+7;

int read(){

    int x=0,f=1;char c=getchar();

    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();

    return f*x;

}

int ksm(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[1000001];

int S(int x,int y){

    int ans=0;

    for(int i=0;i<=y;i++)

        ans=(ans+(i&1?mod-1:1)*jc[y]%mod*ksm(jc[i],mod-2)%mod*ksm(jc[y-i],mod-2)%mod*ksm(y-i,x)%mod)%mod;

    return ans*ksm(jc[y],mod-2)%mod;

}

main(){

    int n=read(),k=read(),ans=0;

    jc[0]=1;

    for(int i=1;i<=n;i++)

        ans=(ans+read())%mod,jc[i]=jc[i-1]*i%mod;

    printf("%lld",(ans*(S(n,k)+S(n-1,k)*(n-1)%mod)%mod)%mod);

    return 0;

}