P1466 集合 Subset Sums【洛谷算法习题】

P1466 集合 Subset Sums

网页链接

P1466 集合 Subset Sums

题目描述

对于从1 ∼ n 1\sim n1∼n的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果n = 3 n=3n=3，对于{ 1 , 2 , 3 } \{1,2,3\}{1,2,3}能划分成两个子集合，每个子集合的所有数字和是相等的：

{ 3 } \{3\}{3}和{ 1 , 2 } \{1,2\}{1,2}是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）

如果n = 7 n=7n=7，有四种方法能划分集合{ 1 , 2 , 3 , 4 , 5 , 6 , 7 } \{1,2,3,4,5,6,7 \}{1,2,3,4,5,6,7}，每一种分法的子集合各数字和是相等的：

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

给出n nn，你的程序应该输出划分方案总数。

输入格式

输入文件只有一行，且只有一个整数n nn。

输出格式

输出划分方案总数。

输入输出样例 #1

输入 #1

7

输出 #1

4

说明/提示

【数据范围】

对于100 % 100\%100%的数据，1 ≤ n ≤ 39 1\le n \le 391≤n≤39。

翻译来自 NOCOW。

USACO 2.2

解题思路

本题是01背包方案计数的经典应用题，通过将等和划分问题转化为子集和计数问题，使用动态规划高效求解。

问题等价转化

将 1~n 的整数集合划分为两个和相等的子集，可按以下步骤推导：

1. 计算全集总和s u m = n ( n + 1 ) 2 sum = \frac{n(n+1)}{2}sum=2n(n+1)​。若 sum 为奇数，无法平分，答案直接为 0。
2. 若 sum 为偶数，设每个子集的目标和为t a r g e t = s u m 2 target = \frac{sum}{2}target=2sum​。问题转化为：从 1~n 中选出若干个数，和恰好为 target，求这样的子集总数。
3. 由于交换两个子集视为同一种划分方案，最终答案等于子集总数除以 2。

动态规划求解子集和计数

采用01背包模型统计方案数：

• 状态定义：dp[i][j]表示从前 i 个数中选取若干个，和恰好为 j 的方案总数。
• 初始边界：dp[0][0] = 1，即不选任何数时，和为 0 的方案有 1 种（空集）。
• 状态转移：对第 i 个数（数值为 i）有两种选择：
  • 不选该数：方案数继承自前 i-1 个数的结果，即dp[i][j] = dp[i-1][j]。
  • 选该数：若 j ≥ i，则加上前 i-1 个数和为 j-i 的方案数，即dp[i][j] += dp[i-1][j-i]。

结果输出

• 若总和为奇数，直接输出 0。
• 否则，总子集方案数为dp[n][target]，最终划分方案数为dp[n][target] / 2。

算法时间复杂度为O ( n 2 ) O(n^2)O(n2)，空间复杂度为O ( n 2 ) O(n^2)O(n2)，n 最大为 39，计算量极小，完全满足题目要求。

总结

核心逻辑：将等和划分问题转化为子集和计数问题，通过01背包动态规划统计符合目标和的子集总数，再除以2得到最终划分方案数。
关键操作：总和奇偶性预判、01背包方案计数递推、对称划分去重处理。
效率保障：n最大39，总运算量仅千级，运行开销极低。

代码简要说明

1. 数组初始化：a数组存储 1~n 的数值，dp二维数组用于存储方案数，全局数组默认初始化为 0，手动设置dp[0][0] = 1作为初始边界。
2. DP递推：外层遍历每个数字，内层遍历所有可能的和，按01背包规则更新方案数。
3. 奇偶判定：若n*(n+1)不能被 4 整除（即总和为奇数），直接输出 0；否则输出dp[n][target]，其中target = n*(n+1)/4。
4. 代码特性说明：
   • 内层循环 j 从 1 开始，未显式维护dp[i][0] = 1，因此仅统计了必须包含数字1的子集方案数。
   • 利用本题连续整数的数学性质：目标和为总和一半时，包含1的子集数恰好等于不包含1的子集数，因此统计结果刚好等于总方案数的一半，即最终答案。
   • 标准通用写法应从 j=0 开始循环以维护空集方案，最后将总方案数除以2，逻辑更严谨且适用于任意数值集合。
5. 输入优化：关闭流同步并解绑 tie，提升输入输出效率。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cin>>n;ll a[45];for(ll i=1;i<=n;i++)a[i]=i;ll dp[45][2010]={};dp[0][0]=1;for(ll i=1;i<=n;i++)for(ll j=1;j<=n*(n+1)/2;j++){dp[i][j]=dp[i-1][j];if(j>=a[i])dp[i][j]+=dp[i-1][j-a[i]];}if(n*(n+1)%4==0)cout<<dp[n][n*(n+1)/4]<<endl;elsecout<<0<<endl;return0;}