题目

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.

Sample Input

7

Sample Output

4

题解

>背包问题 01背包问题<

由于所有数都要用上,因此每一部分数的大小应该是总和的一半
如果总和是 0 必然无解
然后是统计组合个数的背包问题
到达和为 i 可以从 i-j 转移过来
dp[i] += dp[i-j]

n 为 40 的时候结果貌似会溢出 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;
}