《CF961G Partitions》

题目描述

给定一个包含 n 个元素的集合，元素编号从 1 到 n。第 i 个元素的权值为 wi​。某个子集的权值记为

。将该集合划分为 k 个子集的某个划分 R 的权值为

（回忆一下，集合的划分是指将集合划分为若干个子集，使得每个元素恰好属于一个子集）。

请计算将给定集合划分为恰好 k 个非空子集的所有划分的权值之和，并输出其对 109+7 取模的结果。若存在两个元素 x 和 y，在某个划分中属于同一个子集，在另一个划分中属于不同子集，则这两个划分被认为是不同的。

输入格式

第一行包含两个整数 n 和 k（1≤k≤n≤2⋅105），分别表示元素个数和每个划分中的子集个数。

第二行包含 n 个整数 wi​（1≤wi​≤109），表示集合中每个元素的权值。

输出格式

输出一个整数，表示将集合划分为 k 个非空子集的所有划分的权值之和，对 109+7 取模。

显示翻译

题意翻译

输入输出样例

输入 #1复制

4 2 2 3 2 3

输出 #1复制

160

输入 #2复制

5 2 1 2 3 4 5

输出 #2复制

645

说明/提示

第一个样例的所有可能划分如下：

1. {{1,2,3},{4}}，W(R)=3⋅(w1​+w2​+w3​)+1⋅w4​=24；
2. {{1,2,4},{3}}，W(R)=26；
3. {{1,3,4},{2}}，W(R)=24；
4. {{1,2},{3,4}}，W(R)=2⋅(w1​+w2​)+2⋅(w3​+w4​)=20；
5. {{1,3},{2,4}}，W(R)=20；
6. {{1,4},{2,3}}，W(R)=20；
7. {{1},{2,3,4}}，W(R)=26；

第二个样例的所有可能划分如下：

1. {{1,2,3,4},{5}}，W(R)=45；
2. {{1,2,3,5},{4}}，W(R)=48；
3. {{1,2,4,5},{3}}，W(R)=51；
4. {{1,3,4,5},{2}}，W(R)=54；
5. {{2,3,4,5},{1}}，W(R)=57；
6. {{1,2,3},{4,5}}，W(R)=36；
7. {{1,2,4},{3,5}}，W(R)=37；
8. {{1,2,5},{3,4}}，W(R)=38；
9. {{1,3,4},{2,5}}，W(R)=38；
10. {{1,3,5},{2,4}}，W(R)=39；
11. {{1,4,5},{2,3}}，W(R)=40；
12. {{2,3,4},{1,5}}，W(R)=39；
13. {{2,3,5},{1,4}}，W(R)=40；
14. {{2,4,5},{1,3}}，W(R)=41；
15. {{3,4,5},{1,2}}，W(R)=42。

由 ChatGPT 4.1 翻译

代码实现：

#include<bits/stdc++.h> #define N 200000 #define reg register #define inl inline #define int long long using namespace std; const int md=1e9+7; int n,k,s,a[N+5],f[N+5],iv[N+5]; inl int qp(reg int x,reg int y) { reg int res=1; for(;y;y>>=1,x=x*x%md) if(y&1) res=res*x%md; return res; } inl int calc(reg int x,reg int y) { reg int res=0; for(reg int i=0;i<=y;i++) res=(res+((i&1)?md-1:1)*iv[i]%md*qp(y-i,x)%md*iv[y-i]%md)%md; return res; } signed main() { scanf("%lld %lld",&n,&k); for(reg int i=1;i<=n;i++) { scanf("%lld",&a[i]); s=(s+a[i])%md; } f[0]=1; for(reg int i=1;i<=n;i++) f[i]=f[i-1]*i%md; iv[n]=qp(f[n],md-2); for(reg int i=n-1;i>=0;i--) iv[i]=iv[i+1]*(i+1)%md; reg int ans=s*(calc(n,k)+(n-1)*calc(n-1,k)%md)%md; printf("%lld\n",ans); return 0; }