如何计算{1..n}划分为等和两子集的分拆数（模1e9+7）

问题描述 #

需要计算将集合{1, 2, ..., n}划分为两个等和子集的方式数，要求1到n的每个数恰好属于其中一个子集，且两个子集是无序的（即{A,B}与{B,A}视为同一分拆）。

约束条件 #

• n的取值范围为1到500
• 结果需对10⁹+7取模

示例 #

当n=7时，有效的分拆为：

• {1, 3, 4, 6} 和 {2, 5, 7}
• {1, 2, 5, 6} 和 {3, 4, 7}
• {1, 2, 4, 7} 和 {3, 5, 6}
• {1, 6, 7} 和 {2, 3, 4, 5}

答案为4。

已尝试思路 #

我注意到总和S = n(n+1)/2，若S为奇数则答案为0。同时尝试改编经典子集和问题的动态规划方法：

MOD = 10**9 + 7
n = 7
# 思路：dp[i][j] = 从{1..i}中选取和为j的子集的方式数
dp = [[0] * (target + 1) for _ in range(n + 1)]
# 初始化...

但我不确定如何：

1. 避免重复计数镜像分拆
2. 高效处理模运算
3. 从DP表中得到等和分拆的总数

疑问 #

应如何修改或完善该DP以正确计算{1..n}的唯一等和二分拆数？是否有标准技巧（如最终结果减半、容斥原理等）可以使用？

内容的提问来源于stack exchange，提问作者Nam Dương VND18 Vũ