实际上这题的题面还是颇有意思,对两个划分不同的定义暗示了第二类斯特林数,模数是\(1000000007\)又表明这题不是NTT。
那么一开始的想法是考虑每个集合的贡献。设这个集合为\(S\),那么它的贡献为\(|S|\begin{Bmatrix}n-|S|\\k-1 \end{Bmatrix} \sum_{i \in S} w_i\),而所有大小为\(t\)的集合的元素和为\({ {n-1}\choose{t-1}}\sum_{i=1}^n w_i\),故最终答案为\(\sum_{i=1}^n w_i \sum_{j=1}^n j { {n-1}\choose{j-1}} \begin{Bmatrix} n-j\\k-1 \end{Bmatrix}\)。 然后正如评论区里的那位叫\(\color{purple} { \text {Blue233333}}\)老兄所说,这个公式萎了。我们需要考虑新的计数方式。 考虑每个元素的贡献。那么答案就是\(\sum_{i=1}^n w_i \sum_{j=1}^{n} j \times f(n,k,j)\),其中\(f(n,k,j)\)表示把\(n\)个不同元素分到\(k\)个无序的集合中,且标号为1(或者什么别的)的元素所在的集合大小为\(j\)的方案数。 我们记\(g(n,k,i,j)\)表示把\(n\)个不同元素分到\(k\)个无序的集合中,且标号为\(i\)的元素与标号为\(j\)的元素在同一个集合中的方案数。同样地,记\(h(n,k,i,j,s)\)表示把\(n\)个不同元素分到\(k\)个无序的集合中,且标号为\(i\)的元素与标号为\(j\)的元素在同一个大小为\(s\)的集合中的方案数。显然,有\(\sum_{s=1}^n h(n,k,i,j,s) = g(n,k,i,j)\)。 那么,我们有\(j \times f(n,k,j) = \sum_{i=1}^n h(n,k,1,i,j)\),消去了\(j\),这是因为每一种分配方式都被恰好重复计数\(j\)次。故答案等于\(\sum_{j=1}^n g(n,k,1,j)\)。 显然,有\[g(n,k,i,j) = \begin{cases} \begin{Bmatrix} n \\ k \end{Bmatrix}, & \text {if $ i = j $} \\ \begin{Bmatrix} n-1 \\ k \end{Bmatrix}, & \text {if $i \neq j$} \end{cases}\] 那么,答案就是\((\begin{Bmatrix} n \\ k \end{Bmatrix} + (n-1)\begin{Bmatrix} n-1 \\ k \end{Bmatrix}) \sum _ {i=1} ^ n w_i\)。 时间复杂度为\(O(n\log n)\)。 当然,这也就说明了\(\sum_{j=1}^n j { {n-1}\choose{j-1}} \begin{Bmatrix} n-j\\k-1 \end{Bmatrix} = \begin{Bmatrix} n \\ k \end{Bmatrix} + (n-1)\begin{Bmatrix} n-1 \\ k \end{Bmatrix}\)。希望有大佬给出这个的代数证明。#include小结:在组合计数问题上另辟蹊径,除解题之外还能带来奇妙的结论。using namespace std;const int MOD = 1e9 + 7, N = 200010;typedef long long ll;ll power(ll a,int b) { ll res = 1ll; while (b) { if (b&1) (res *= a) %= MOD; (a *= a) %= MOD; b >>= 1; } return res;}ll jc[N],inv[N],sum,ans;ll comb(int a,int b) { return (a < 0 || b < 0 || a < b) ? 0 : \ jc[a] * inv[a-b] % MOD * inv[b] % MOD;}int n,k,w;int main() { scanf("%d%d",&n,&k); for (int i = 1 ; i <= n ; ++ i) scanf("%d",&w), (sum += w) %= MOD; jc[0] = 1ll; for (int i = 1 ; i <= n ; ++ i) jc[i] = jc[i-1] * i % MOD; inv[n] = power(jc[n],MOD - 2); for (int i = n-1 ; i >= 0 ; -- i) inv[i] = inv[i+1] * (i+1) % MOD; for (int i = 1, j = (k&1) ? 1 : -1 ; i <= k ; ++ i, j = -j) { ans += j * comb(k,i) * power(i,n-1) % MOD; ans = (ans % MOD + MOD) % MOD; } (ans *= n-1) %= MOD; for (int i = 1, j = (k&1) ? 1 : -1 ; i <= k ; ++ i, j = -j) { ans += j * comb(k,i) * power(i,n) % MOD; ans = (ans % MOD + MOD) % MOD; } (ans *= sum) %= MOD; (ans *= inv[k]) %= MOD; cout << ans << endl; return 0;}