CF961G Partitions

CF961G Partitions题解

题意:

给出(n) 个物品, 每个物品有一个权值(w_i)

定义一个集合(S) 的权值(W(S)=|S|sumlimits_{xin S}w_x)

定义一个划分的权值为(W'(R)=sumlimits_{Ssubseteq R}W(S))

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

(n,kle2 imes10^5,w_ile10^9)

题解:

首先看出每个物品"地位"相同, 对答案的贡献肯定是(W_i*K)的形式, 所有的K都相等, 所以只需求出物品一的K就行

一个比较显然((naive))的想法, 枚举物品一所在集合大小

[K = sum_{i=1}^ni * large {left(^{n-1}_{i-1} ight)}*large{left{_{k-1}^{n-i} ight}} ]

如果你是推式子带师, 可以一推, 但想我这样蒟蒻只能另辟蹊径

在一种划分方案中, 物品一的贡献为它所在集合大小, 相当于它对本集和中的所有点都有贡献, 它自己对自己的贡献显然是划分的方案数(left{^n_k ight}), 对其他点的贡献相当于把剩下(n-1)个点划分, 再将其放入任意集合中, 即对所有集合中的点均有贡献, 所以答案为

[large{Ans = (sum_{i=1}^nw_i)(left{^n_k ight}+(n+1)left{^{n-1}_{~~k} ight})} ]

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int P = 1e9+7;

ll fpw(ll x, ll mi) {
	ll res = 1;
	while (mi) {
		if (mi & 1) res = res * x % P;
		x = x * x % P;
		mi >>= 1;
	}
	return res;
}

template <typename T>
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

template <typename T>
void write(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x >= 10) write(x / 10);
    putchar('0' + x % 10);
}

const int N = 500050;
ll jie[N], inv[N];
void prework(void) {
	const int Maxn = 300000;
	jie[0] = jie[1] = inv[0] = inv[1] = 1;
	for (int i = 2;i <= Maxn; i++) 
		jie[i] = jie[i-1] * i % P, 
		inv[i] = (P - P / i) * inv[P % i] % P;
	for (int i = 2;i <= Maxn; i++) inv[i] = inv[i-1] * inv[i] % P;
}


ll strling(ll n, ll m) {
	if (m > n) return 0;
	ll ans = 0;
	for (int i = 0;i <= m; i++) {
		if ((m - i) & 1) ans -= fpw(i, n) * inv[i] % P * inv[m-i] % P;
		else ans += fpw(i, n) * inv[i] % P * inv[m-i] % P;
		ans %= P;
	}
	return (ans + P) % P;
}

ll sum;
int main() {
	prework();
	int n, k; read(n), read(k);
	for (int i = 1;i <= n; i++) {
		ll x; read(x); sum += x;
	}
	sum %= P;
	sum = sum * (strling(n, k) + (n - 1) * strling(n - 1, k) % P) % P;
	cout << sum << endl;
	return 0;
}