Problem

對于由從1到N (1 <= N <= 39)這N個連續(xù)的整數(shù)組成的集合來說，我們有時可以將集合分成兩個部分和相同的子集合。
例如，N=3時，可以將集合{1, 2, 3} 分為{1,2}和{3}。此時稱有一種方式（即與順序無關(guān)）。
N=7時，共有四種方式可以將集合{1, 2, 3, ..., 7} 分為兩個部分和相同的子集合：
{1,6,7} 和 {2,3,4,5}
{2,5,7} 和 {1,3,4,6}
{3,4,7} 和 {1,2,5,6}
{1,2,4,7} 和 {3,5,6}
輸入：程序從標準輸入讀入數(shù)據(jù)，只有一組測試用例。如上所述的N。
輸出：方式數(shù)。若不存在這樣的拆分，則輸出0。

test input

7

test output

4

ac code

//
//  main.cpp
//  和相同的子集合
//
//  Created by jetviper on 2017/3/24.
//  Copyright ? 2017年 awlsx. All rights reserved.
//

#include<iostream>
#include <stdio.h>


int dp[200];

int main()
{
    for (int i=0; i<200; i++) {
        dp[i]=0;
    }
    int n;
    scanf("%d",&n);
    
    int res = n*(n+1)/2;
    
    if(res%2)
    {
        printf("0\n");
        return 0;
    }
    res/=2;
   
    dp[0]=1;
    
    for(int i=1;i<=n;i++)
        for(int j=res;j>=i;j--)dp[j]+=dp[j-i];////dp[j]表示加起來等于j的組數(shù)
    

    printf("%d\n",dp[res]/2);
    return 0;
}