[Codeforces961G]Partitions

题意

给出 n n 个物品,, 每个物品有一个权值 wi w i

定义一个集合 S S 的权值W(S)=|S|∑x∈SwxW(S)=|S|∑x∈Swx

定义一个划分的权值为 W′(R)=∑S⊆RW(S) W ′ ( R ) = ∑ S ⊆ R W ( S )

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

n,k≤2×105,wi≤109 n , k ≤ 2 × 10 5 , w i ≤ 10 9

---

题解

考虑把每一个元素的贡献加起来

不难发现每个元素前的系数都是一样的 , , 设系数是pp

Ans=p∑i=1nwi A n s = p ∑ i = 1 n w i

考虑枚举 i i 所在的集合的大小(S(S表示第二了斯特林数 ), ) , 那么

p=∑s=1ns(n−1s−1)Sk−1n−s p = ∑ s = 1 n s ( n − 1 s − 1 ) S n − s k − 1

考虑到 Smn=1m!∑i=0m(−1)i(mi)(m−i)n S n m = 1 m ! ∑ i = 0 m ( − 1 ) i ( m i ) ( m − i ) n

=∑s=1ns(n−1s−1)∑i=0k−1(−1)i(k−1)!(k−1i)(k−i−1)n−s = ∑ s = 1 n s ( n − 1 s − 1 ) ∑ i = 0 k − 1 ( − 1 ) i ( k − 1 ) ! ( k − 1 i ) ( k − i − 1 ) n − s

=∑s=1ns(n−1s−1)∑i=0k−1(−1)ii!(k−i−1)n−s(k−i−1)! = ∑ s = 1 n s ( n − 1 s − 1 ) ∑ i = 0 k − 1 ( − 1 ) i i ! ( k − i − 1 ) n − s ( k − i − 1 ) !

=∑i=0k−1(−1)ii!(k−i−1)!∑s=1ns(n−1s−1)(k−i−1)n−s = ∑ i = 0 k − 1 ( − 1 ) i i ! ( k − i − 1 ) ! ∑ s = 1 n s ( n − 1 s − 1 ) ( k − i − 1 ) n − s

考虑 ∑ns=1s(n−1s−1)(k−i−1)n−s ∑ s = 1 n s ( n − 1 s − 1 ) ( k − i − 1 ) n − s

=∑s=1n(n−1s−1)(k−i−1)n−s+∑s=1n(s−1)(n−1s−1)(k−i−1)n−s = ∑ s = 1 n ( n − 1 s − 1 ) ( k − i − 1 ) n − s + ∑ s = 1 n ( s − 1 ) ( n − 1 s − 1 ) ( k − i − 1 ) n − s

考虑到 k(nk)=n(n−1k−1) k ( n k ) = n ( n − 1 k − 1 )

=∑s=1n(n−1s−1)(k−i−1)n−s+(n−1)∑s=1n(n−2s−2)(k−i−1)n−s = ∑ s = 1 n ( n − 1 s − 1 ) ( k − i − 1 ) n − s + ( n − 1 ) ∑ s = 1 n ( n − 2 s − 2 ) ( k − i − 1 ) n − s

考虑到 ∑i=0n(ni)(k−1)n−i=kn ∑ i = 0 n ( n i ) ( k − 1 ) n − i = k n

=(k−i)n−1+(n−1)(k−i)n−2 = ( k − i ) n − 1 + ( n − 1 ) ( k − i ) n − 2

=(k−i)n−2(k−i+n−1) = ( k − i ) n − 2 ( k − i + n − 1 )

⇒p=∑i=0k−1(−1)i(k−i)n−2i!(k−i−1)!(k−i+n−1) ⇒ p = ∑ i = 0 k − 1 ( − 1 ) i ( k − i ) n − 2 i ! ( k − i − 1 ) ! ( k − i + n − 1 )

O(klogk) O ( k log ⁡ k ) 递推即可

#include<bits/stdc++.h> #define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i) #define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to) #define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char ss[1<<17],*A=ss,*B=ss; inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;} template<class T>inline void sd(T&x){ char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48; while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y; } const int N=2e5+5,P=1e9+7; typedef int arr[N]; typedef long long ll; int n,k,Sum;arr fac,ifac;ll p; inline int pls(int a,int b){return a+=b,a<P?a:a-P;} inline int fpm(int a,int b){if(b<0)return 1;int x=1;for(;b;b>>=1,a=(ll)a*a%P)if(b&1)x=(ll)x*a%P;return x;} int main(){ #ifndef ONLINE_JUDGE file("s"); #endif sd(n),sd(k);int x; fp(i,1,n)sd(x),Sum=pls(Sum,x); fac[0]=1;fp(i,1,n)fac[i]=(ll)fac[i-1]*i%P; ifac[n]=fpm(fac[n],P-2);fd(i,n,0)ifac[i-1]=(ll)ifac[i]*i%P; fp(i,0,k-1)p+=(i&1?-1:1)*(ll)ifac[i]*ifac[k-i-1]%P*fpm(k-i,n-2)%P*(k-i+n-1)%P; printf("%lld\n",(ll)pls(p%P,P)*Sum%P); return 0; }

然后你可以发现这玩意根本推不出来好吗,于是就有另外一种比较容易的方法

注意到 W(S)=|S|∑x∈Swx, W ( S ) = | S | ∑ x ∈ S w x , 前面的系数是 |S|, | S | , 对于 i∈S i ∈ S 可以当做 |S| | S | 中每个数都对 i i 产生了一次贡献

那么我们只要枚举每一个数对ii的贡献即可

i i 对自身的贡献显然是SknSnk

j≠i j ≠ i 时 ,j , j 对 i i 的贡献是jj和 i i 在同一个集合的方案数,,也就是 Skn−1 S n − 1 k

于是 p=Skn+(n−1)Skn−1 p = S n k + ( n − 1 ) S n − 1 k 其实也可以从上面那些东西推出来的

用 Smn=1m!∑i=0m(−1)i(mi)(m−i)n=∑i=0m(−1)ii!(m−i)n(m−i)!,O(klogk) S n m = 1 m ! ∑ i = 0 m ( − 1 ) i ( m i ) ( m − i ) n = ∑ i = 0 m ( − 1 ) i i ! ( m − i ) n ( m − i ) ! , O ( k log ⁡ k ) 算就好了

#include<bits/stdc++.h> #define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i) #define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to) #define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char ss[1<<17],*A=ss,*B=ss; inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;} template<class T>inline void sd(T&x){ char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48; while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y; } const int N=2e5+5,P=1e9+7; typedef int arr[N]; typedef long long ll; int n,k,Ans;arr fac,ifac; inline int pls(int a,int b){return a+=b,a<P?a:a-P;} inline int fpm(int a,int b){int x=1;for(;b;b>>=1,a=(ll)a*a%P)if(b&1)x=(ll)x*a%P;return x;} inline int S(int n,int m){ ll tp=0; fp(i,0,m)tp+=(i&1?-1:1)*(ll)fpm(m-i,n)*ifac[m-i]%P*ifac[i]%P; return pls(tp%P,P); } int main(){ #ifndef ONLINE_JUDGE file("s"); #endif sd(n),sd(k);int x; fp(i,1,n)sd(x),Ans=pls(Ans,x); fac[0]=1;fp(i,1,n)fac[i]=(ll)fac[i-1]*i%P; ifac[n]=fpm(fac[n],P-2);fd(i,n,0)ifac[i-1]=(ll)ifac[i]*i%P; Ans=(ll)Ans*pls(S(n,k),(ll)(n-1)*S(n-1,k)%P)%P; printf("%d\n",Ans); return 0; }