435_temp.cpp

/*
	Число называется счастливым, если какие-то определенные его цифры можно сложить так, чтобы получить половину суммы всех цифр.

	Зафиксируем определенный набор цифр длины N. Количество чисел, получающихся из этого набора, равно n!/n_0!/n_1!/n_2!/.../n_k!, где n_k - количество k-й цифры в наборе.

	Сумму, которую можно достичь, определяем из соображений динамического программирования.
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cmath>

typedef long long Number;

void check(bool q) {
	if (!q) {
		throw 1;
	}
}

Number fact(int n) {
	check(n >= 0);
	return n <= 1 ? 1 : fact(n-1) * n;
}

Number C(int n, int k) {
	return fact(n) / fact(k) / fact(n-k);
}

bool is_good_set(const std::vector<int>& set) {
	int sum = 0;
	for (int i = 0; i < (int)set.size(); ++i) {
		sum += i * set[i];
	}
	if (sum % 2 == 1) return false;
	std::bitset<301> is_sum(1);
	for (int i = 0; i <= (int)set.size(); ++i) {
		for (int c = 1; c <= set[i]; ++c) {
			is_sum |= (is_sum << i);
		}
	}
	return is_sum[sum / 2];
}

void rec(int count, int curr_digit, int max_digit, std::vector<int>& set, int n, Number& answ) {
	if (curr_digit == max_digit) {
		set[curr_digit] = count;
		if (is_good_set(set)) {
			Number temp = fact(n);
			for (int i = 0; i <= max_digit; ++i) {
				temp /= fact(set[i]);
			}
			answ += temp;
			/*
			for (int i = 1; i <= max_digit; ++i) {
				printf(" %d[%d]", i, set[i]);
			}
			printf("\n");

			std::cout << temp << std::endl;
			*/
		}

		return;
	}

	for (int c = count; c >= 0; --c) {
		//printf(" %d[%d]", curr_digit, c);
		set[curr_digit] = c;
		rec(count-c, curr_digit+1, max_digit, set, n, answ);
	}
}

Number fast_answer_without_zeros(int n, int k) {
	//printf("--- fast_answer_without_zeros(%d, %d) \n", n, k);
	Number answ = 0;
	std::vector<int> set(1+k);
	rec(n, 1, k, set, n, answ);
	return answ;
}

Number fast_answer_with_zeros(int n, int k) {
//	printf("--- fast_answer_with_zeros(%d, %d) \n", n, k);

	Number answ = 0;
	for (int zeros = 0; zeros <= n; ++zeros) {
		answ += fast_answer_without_zeros(n-zeros, k) * C(n, zeros);
	}
	return answ;
/*
	Number answ = 0;
	std::vector<int> set(1+k);
	rec(n, 0, k, set, n, answ);
	return answ;
*/
}

bool next(std::vector<int>& digits, int max_digit) {
	int i = 0;
	while (i < (int)digits.size() && digits[i] == max_digit) {
		digits[i] = 0;
		++i;
	}
	if (i == (int)digits.size()) {
		return false;
	}
	++digits[i];
	return true;
}

std::vector<int> get_set(const std::vector<int>& digits, int max_digit) {
	std::vector<int> set(1+max_digit);
	for (auto d : digits) {
		++set[d];
	}
	return set;
}

Number slow_answer(int n, int k) {
	Number answer = 0;
	std::vector<int> digits(n, 0);
	do { /*
		printf("digits: ");
		for (int i = n-1; i >= 0; --i) {
			printf("%d", digits[i]);
		}
		printf("\n");
		printf("   set: ");
		*/
		auto set = get_set(digits, k);
		/*
		for (int i = 0; i <= k; ++i) {
			printf("%d(%d) ", i, set[i]);
		}
		printf("\n");
		*/
		if (is_good_set(set)) {
			/*
			for (int i = 0; i < (int)set.size(); ++i) {
				printf(" %d(%d)", i, set[i]);
			}
			printf("\n");
			*/
			answer++;
		}
		/*
		for (int i = (int)digits.size()-1; i >= 0; --i) {
			printf("%d", digits[i]);
		}
		printf("\n");
		*/
	} while (next(digits, k));
	return answer;
}

int main() {
	int n = 11, k = 9;
	//std::cout << (long long)(std::pow(k+1ll,n)) << std::endl;
	std::cout << (long long)(std::pow(k+1ll, n) - fast_answer_with_zeros(n, k)) << std::endl;
	std::cout << (long long)(std::pow(k+1ll, n) - slow_answer(n,k)) << std::endl;

	/*
	std::vector<int> count(1+k, 0);
	rec(n, 1, k, count);
	*/
	/*
	int n, k;
	std::cin >> n >> k;

	auto answ = fast_answer_with_zeros(n, k);
	std::cout << answ;
	*/
	return 0;
}