<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
For many sets of consecutive integers from 1 through N (1 &lt;= N &lt;= 39), one can partition the set into two sets whose sums are identical.
For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical:
{3} and {1,2} 
This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions).
If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum:
{1,6,7} and {2,3,4,5} 
{2,5,7} and {1,3,4,6} 
{3,4,7} and {1,2,5,6} 
{1,2,4,7} and {3,5,6} 
Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.
Your program must calculate the answer, not look it up from a table.
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
The input file contains a single line with a single integer representing N, as above.
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
The output file contains a single line with a single integer that tells how many same-sum partitions can be made from the set {1, 2, ..., N}. The output file should contain 0 if there are no ways to make a same-sum partition.
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
7
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
4
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
<a href="/post/Algorithm/Package_Problem.html#01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98">&gt;背包问题 01背包问题&lt;</a>
由于所有数都要用上,因此每一部分数的大小应该是总和的一半 
如果总和是 <code>0</code> 必然无解 
然后是统计组合个数的背包问题 
到达和为 <code>i</code> 可以从 <code>i-j</code> 转移过来 
<code>dp[i] += dp[i-j]</code>
<code>n</code> 为 <code>40</code> 的时候结果貌似会溢出 <code>int</code> 以防万一用了 <code>long long</code>
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com
 
かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
#include &lt;set&gt;
#include &lt;functional&gt;
#include &lt;bitset&gt;
using namespace std;
 
const int maxn = 1000;
 
int v;
long long dp[maxn];
 
void ZeroOnePack(int cost,int weight) {
 for(int i = v; i &gt;= cost; i--)
 dp[i] += dp[i - cost];
}
 
bool Do() {
 int n;
 if(!(cin &gt;&gt; n))
 return false;
 
 v = (1 + n)*n / 2;
 
 if(v &amp; 1) {
 cout &lt;&lt; 0 &lt;&lt; endl;
 } else {
 v /= 2;
 memset(dp,0,sizeof(dp));
 dp[0] = 1;
 for(int i = 1;i &lt;= n;i++) {
 ZeroOnePack(i,i);
 }
 cout &lt;&lt; dp[v] / 2 &lt;&lt; endl;
 }
 return true;
}
int main() {
 cin.tie(0);
 cin.sync_with_stdio(false);
 
 while(Do());
 return 0;
}
</pre>

AOJ 400.Subset Sums