Решение задачи Разбиения с Codeforces

С пояснением   Просмотров: 24


Дано множество из n элементов, пронумерованных от 1 до n. Вес i-го объекта равен w i. Вес некоторого подмножества этого множества рассчитывается по формуле . Вес разбиения R данного множества на k подмножеств равен (напоминаем, разбиением называется множество таких подмножеств данного множества, что каждый элемент данного множества принадлежит ровно одному множеству из разбиения).

Посчитайте суммарный вес всех различных разбиений данного множества на k непустых подмножеств по модулю 109 + 7. Два разбиения считаются различными, если существуют два объекта x и y, такие, что в одном разбиении они принадлежат разным множествам, а в другом — одному и тому же.

Код

#include <bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) fore(i, 0, n)

const int MOD = int(1e9) + 7;

inline int norm(int a) {
	while(a >= MOD)
		a -= MOD;
	while(a < 0)
		a += MOD;
	return a;
}

inline int mul(int a, int b) {
	return int((a * 1ll * b) % MOD);
}

inline int binPow(int a, int k) {
	int ans = 1;
	while(k > 0) {
		if(k & 1) ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}

const int N = 200 * 1000 + 555;

int f[N], inf[N];

void precalc() {
	f[0] = inf[0] = 1;
	fore(i, 1, N) {
		f[i] = mul(f[i - 1], i);
		inf[i] = mul(inf[i - 1], binPow(i, MOD - 2));
	}
}

int n, k, w[N];

inline bool read() {
	if(!(cin >> n >> k))
		return false;
	forn(i, n)
		cin >> w[i];
	return true;
}

inline int c(int n, int k) {
	if(k > n || n < 0) return 0;
	if(k == 0 || n == k) return 1;
	
	return mul(f[n], mul(inf[n - k], inf[k]));
}

inline int s(int n, int k) {
	if(n == 0) return k == 0;
	if(k == 0) return n == 0;
	
	int ans = 0, sg[2] = {1, MOD - 1};
	forn(cnt, k)
		ans = norm(ans + mul(sg[cnt & 1], mul(c(k, cnt), binPow(k - cnt, n))));
	return mul(ans, inf[k]);
}

inline void solve() {
	int sum = 0;
	forn(i, n)
		sum = norm(sum + w[i]);
		
	int s0 = s(n, k);
	int s1 = mul(n - 1, s(n - 1, k));
	
	cout << mul(sum, norm(s0 + s1)) << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	precalc();
	
	assert(read());
	solve();

#ifdef _DEBUG
	cerr << "TIME = " << clock() << endl;
#endif
	return 0;
}

         

Администратор Photo Автор: Администратор


Для того, чтобы эффективно решать данную задачу, заметим следующие факты. Во-первых, результирующий ответ будет состоять из суммы весов объектов w i, взятых с некоторыми коэффициентами cf i, и, следовательно, задачу можно свести к подсчету этих коэффициентов.

Тогда cf i можно посчитать перебрав размер подмножества, в который попадет объект i, а именно: , где f(n, k, size) — количество разбиений множества из n на k подмножеств, где одно из них имеет размер size, и в нем находится i.

Данный способ не очень эффективен, поэтому заметим следующий факт: каждый элемент j, попав в одно подмножество с элементом i увеличит размер данного подмножества на 1, и, соответственно, коэффициент при w i. Тогда для i-го объекта достаточно перебрать объект j, который попадет с ним в одно подмножество, т.е . g(n, k, i, j) — количество способов разбить множество из n элементов на k подмножеств так, чтобы i-й и j-й находились в одном подмножестве.

Для подсчета g(n, k, i, j) воспользуемся числами Стирлинга второго рода: — кол-во способов разбить множество из n элементов на k непустых подмножеств. Если i = j, то , иначе просто объединим i и j в один объект и .

Финальная формула примет следующий вид: . Ответ в таком случае равен .

Для подсчета чисел Стирлинга можно воспользоваться формулой включения-исключения, которую несложно вывести либо найти в Википедии: .

Результирующая асимптотика — O(nlog(n)).


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться