305080: CF961G. Partitions
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Partitions
题意翻译
给出 $n$ 个物品,每个物品有一个权值 $w_i$。 定义一个集合 $S$ 的权值 $W(S)=|S|\sum\limits_{x\in S}w_x$。 定义一个划分的权值为 $W'(R)=\sum\limits_{S\in R}W(S)$。 求将 $n$ 个物品划分成 $k$ 个集合的所有方案的权值和。答案对 $10^9+7$ 取模。 $n,k\le2\times10^5$,$w_i\le10^9$。 感谢 @Kelin 提供的翻译题目描述
You are given a set of $ n $ elements indexed from $ 1 $ to $ n $ . The weight of $ i $ -th element is $ w_{i} $ . The weight of some subset of a given set is denoted as ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF961G/fbf0c843290b6183affbaf7ada0d6cecd6d2fbbd.png). The weight of some partition $ R $ of a given set into $ k $ subsets is ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF961G/0aeb77393cfc4b9aa3d9c64303202277f9c1f051.png) (recall that a partition of a given set is a set of its subsets such that every element of the given set belongs to exactly one subset in partition). Calculate the sum of weights of all partitions of a given set into exactly $ k $ non-empty subsets, and print it modulo $ 10^{9}+7 $ . Two partitions are considered different iff there exist two elements $ x $ and $ y $ such that they belong to the same set in one of the partitions, and to different sets in another partition.输入输出格式
输入格式
The first line contains two integers $ n $ and $ k $ ( $ 1<=k<=n<=2·10^{5} $ ) — the number of elements and the number of subsets in each partition, respectively. The second line contains $ n $ integers $ w_{i} $ ( $ 1<=w_{i}<=10^{9} $ )— weights of elements of the set.
输出格式
Print one integer — the sum of weights of all partitions of a given set into $ k $ non-empty subsets, taken modulo $ 10^{9}+7 $ .
输入输出样例
输入样例 #1
4 2
2 3 2 3
输出样例 #1
160
输入样例 #2
5 2
1 2 3 4 5
输出样例 #2
645