Как подсчитать количество подмножество разделов {1..n} на два подмножества с равными суммами (Modulo 10⁹+7) ⇐ C++

[Anonymous]

Я работаю над проблемой комбинаторики, где мне нужно вычислить, сколько способов, которыми набор {1, 2, ..., n} может быть разделен на два подмножества с одинаковой суммой , так что каждое число от 1 до N находится в одном из двух подмножеств. Два подмножества неупорядочены (т.е. {a, b} считаются такими же, как {b, a} ).
ограничения :

Код: Выделить всё

n

составляет от 1 до 500.

Код: Выделить всё

{1, 3, 4, 6} and {2, 5, 7}
{1, 2, 5, 6} and {3, 4, 7}
{1, 2, 4, 7} and {3, 5, 6}
{1, 6, 7} and {2, 3, 4, 5}

Итак, ответ 4 .
Что я попробовал:
Я заметил общую сумму s = n (n+1)/2 , и если s нечетный, ответ - 0 . Я также попытался адаптировать динамический подход программирования, аналогичный классической подмножеством.MOD = 10**9 + 7
n = 7
# Idea: dp[j] = number of ways to pick a subset from {1..i} with sum j
dp = [[0] * (target + 1) for _ in range(n + 1)]
# Initialize...
< /code>
Но я не уверен, как: < /p>

Избегайте переосмысления зеркальных разделов. /> Вопрос: < /h3>
Как мне изменить или заполнить этот DP, чтобы правильно считать уникальные двусмысленные двусторонние двойники {1..n} < /code>? Есть ли стандартный трюк (например, вдвое окончательное количество, включение-эксклюзия и т. Д.) Я должен использовать здесь?

Подробнее здесь: https://stackoverflow.com/questions/796 ... sum-subset