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.

PROGRAM NAME: subset

INPUT FORMAT

SAMPLE INPUT (file subset.in)

7

OUTPUT FORMAT

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 OUTPUT (file subset.out)

4

題意：
對給出的n，從1到n里挑出一些數(shù)使它們的和等于沒挑過的數(shù)字之和。求滿足這樣條件的組數(shù)。
代碼如下：

/*
LANG: C
TASK: subset
*/
#include<stdio.h>
long long dp[40][400];
int main()
{
    freopen("subset.in", "r", stdin);
    freopen("subset.out", "w", stdout);
    int n, sum, i, j;
    scanf("%d", &n);
    sum = n * (n + 1);
    if ( sum / 2 & 1)//如果所有的和sum/2為奇數(shù)。就沒有符合題意的。 
    {
        printf("0\n");
    }
    else
    {
        //dp[i,j]表示在前i個數(shù)里能組成和為j的組數(shù) 
        sum /= 4;
        dp[0][0] = 1;
        for (i = 1; i <= sum; i++)
        {
            dp[0][i] = 0;//因?yàn)橄聵?biāo)最低為0.預(yù)先處理。 
        }
        for (i = 1; i <= n; i++)
        {
            for (j = 0; j <= sum; j++)
            {
                //dp[i,j]有兩種組合情況，一種是前i-1個數(shù)里組成和為j的組數(shù)
                //一種是前i-1個數(shù)里組成和為j-i的組數(shù)，這樣dp[i-1, j-i]加上j本身也是屬于和為j的情況。 
                if (j < i)//確保j-i>=0 
                {
                    dp[i][j] = dp[i-1][j];
                }
                else
                {
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-i];
                }
            }
        }
        printf("%lld\n", dp[n][sum]/2);//因?yàn)槭乔蟪鏊星闆r。所以要除二 
    }
    fclose(stdin);
    fclose(stdout);
    //system("pause");
    return 0;
}