271

# 题目

## Description

For many sets of consecutive integers from 1 through N (1 <= N <= 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.

## Input

The input file contains a single line with a single integer representing N, as above.

## Output

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.

7

4

# 题解

**>背包问题 01背包问题<**

dp[i] += dp[i-j]

n40 的时候结果貌似会溢出 int 以防万一用了 long long

# 代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！

*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <bitset>
using namespace std;

const int maxn = 1000;

int v;
long long dp[maxn];

void ZeroOnePack(int cost,int weight) {
for(int i = v; i >= cost; i--)
dp[i] += dp[i - cost];
}

bool Do() {
int n;
if(!(cin >> n))
return false;

v = (1 + n)*n / 2;

if(v & 1) {
cout << 0 << endl;
} else {
v /= 2;
memset(dp,0,sizeof(dp));
dp[0] = 1;
for(int i = 1;i <= n;i++) {
ZeroOnePack(i,i);
}
cout << dp[v] / 2 << endl;
}
return true;
}
int main() {
cin.tie(0);
cin.sync_with_stdio(false);

while(Do());
return 0;
}

• 点击查看/关闭被识别为广告的评论