游客 注册 | 登录
中文 | En

3745 - 集合划分

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

对于从1到N（1<=N<=39）的连续整数集合，划分成两个子集合，使得每个集合的数字之和相等。

举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：{3} and {1,2}

这是唯一的一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）。

如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分法的子集合各数字和是相等的:

{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}

题目输入

一个正整数N，1<=N<=39

题目输出

一个数，划分集合的方法数。

输入/输出样例

输入格式

7

输出格式

4

C++解答

#include<cstdio>
#include<cstring>
#define clr(x)memset(x,0,sizeof(x))
long long f[50000];
int main()
{
    long long n,i,j,v;
    while(scanf("%lld",&n)!=EOF)
    {
        if(n==0)
        break;
        v=n*(n+1)/2;
        if(v%2==1)
        {
            printf("0\n");
            continue;
        }
        clr(f);
        f[0]=1;
        v/=2;
        for(i=1;i<=n;i++)
            for(j=v;j>=i;j--)
                f[j]+=f[j-i];
        printf("%lld\n",f[v]/2);
    }
    return 0;
}
请先登陆