CF961G Partitions（斯特林数+二项式定理）

· · 题解

CF961G Partitions

拆开计算每个物品的贡献，容易得到

\begin{aligned}ans=&\sum\limits_{i=1}^nw_i\sum\limits_{s=1}^ns{n-1\choose s-1}{n-s\brace k-1}\\\end{aligned}

法一：直接无脑MTT（然而我不会）

法二（暴力推式子）：前半部分可以直接加起来，化开后半部分

\begin{aligned}&\sum\limits_{s=1}^ns{n-1\choose s-1}{n-s\brace k-1}\\=&\sum\limits_{s=1}^ns{n-1\choose s-1}\sum\limits_{i=0}^{k-1}\frac{(-1)^{k-1-i}}{(k-1-i)!}\frac{i^{n-s}}{i!}\\=&\sum\limits_{i=0}^{k-1}\frac{(-1)^{k-1-i}}{(k-1-i)!i!}\sum\limits_{s=1}^ns{n-1\choose s-1}i^{n-s}\\\end{aligned}

如果没有 \times s ，后半部分就是一个二项式反演的形式。于是把 s 拆开

\begin{aligned}&\sum\limits_{s=1}^ns{n-1\choose s-1}i^{n-s}\\=&\sum\limits_{s=1}^n(s-1){n-1\choose s-1}i^{n-s}+\sum\limits_{s=1}^n{n-1\choose s-1}i^{n-s}\\=&(n-1)\sum\limits_{s=1}^n{n-2\choose s-2}i^{n-s}+(i+1)^{n-1}\\=&(n-1)(i+1)^{n-2}+(i+1)^{n-1}\\=&(i+1)^{n-2}(n+i)\end{aligned}

代回原式，设 sum=\sum w_i，即

ans=sum\sum\limits_{i=0}^{k-1}\frac{(-1)^{k-1-i}}{(k-1-i)!i!}(i+1)^{n-2}(n+i)

法三（更聪明的做法，考虑组合意义）：

对于 i\in S ，|S| 这个系数可以看作 S 中的所有物品都对 S 产生了 1 的贡献。j 对 i 的贡献即 j,i 被分在同一个集合的方案数： j=i 时产生 n\brace k 的贡献，j\neq i 时产生 n-1\brace k 的贡献。即（其实化开和上面一样）：

ans=sum({n\brace k}+(n-1){n-1\brace k}) 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FGF
{
    int n,m;
    const int mo=1e9+7,N=2e5+5;
    int qpow(int x,int y)
    {
        int s=1;
        while(y)
        {
            if(y&1)s=1ll*s*x%mo;
            x=1ll*x*x%mo;
            y>>=1;
        }
        return s;
    } 
    int sum,ans,fac[N];
    void work()
    {
        scanf("%d%d",&n,&m);
        fac[0]=1;
        for(int i=1,a;i<=n;i++)
            scanf("%d",&a),sum=(sum+a)%mo;
        if(n==1){printf("%d\n",sum);return;}
        for(int i=1;i<=m;i++)
            fac[i]=1ll*fac[i-1]*i%mo;
        fac[m]=qpow(fac[m],mo-2);
        for(int i=m-1;i;i--)
            fac[i]=1ll*fac[i+1]*(i+1)%mo;
        for(int i=0;i<m;i++)
            ans=(ans+((m-i-1)&1? -1ll:1ll)*fac[m-i-1]*fac[i]%mo*qpow(i+1,n-2)%mo*(n+i)%mo+mo)%mo; 
        printf("%lld",1ll*sum*ans%mo);
    }
}
int main()
{
    FGF::work();
    return 0;
}