学步园

集合

Description

对于从1到N的连续整集合，能划分成两个子集合，且保证每个集合的数字和是相等的。例如：如果N=3，对于｛1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：{3} and {1,2} ，且这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）。

又例如：如果N=7，集合{1，2，3，4，5，6，7}有如下四种划分方法：

(1)、{1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}

(2)、{2,5,7} and {1,3,4,6}

(3)、{3,4,7} and {1,2,5,6}

(4)、{1,2,4,7} and {3,5,6}

给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。

Input

　只有一行，且只有一个整数N

Output

　输出划分方案总数，如果不存在则输出0。

Sample Input

　7

Sample Output

　4

 1 #include<stdio.h>
#include<stdlib.h>
#include<string.h>
 long long   f[10000];
int n;
int main(){
    FILE *in,*out;
    in=fopen("input6.txt","r");
    out=fopen("output.txt","w");
    fscanf(in,"%d",&n);  
    if(((n*n+n)/2)%2==1)
    {
    fprintf(out,"0\n");
    printf("0\n");
    } 
    else 
    {
    int i,j;
    memset(f,0,sizeof(f));   
    f[1]=1; 
    for(i=2;i<=n;i++)
    for(j=(n*n+n)/4;j>=1;j--)
    {
    if(j>i)
    f[j]=f[j]+f[j-i];
    if(j==i) f[j]++;
    }
    
    printf("%d\n",f[(n*n+n)/4]/2);
    fprintf(out,"%d\n",f[(n*n+n)/4]/2);
     }
     system("pause");
     fclose(in);
     fclose(out);
     return 0;
     }


     转移方程： f[i][j]=f[i-1][j]+f[i-1][j-i]， 
     程序思想：f[i][j]代表前i个数表示j有多少种方法，它等于前i-1个数表示j的方法数，加上前i-1个数，表示j-i的方法数
     需要注意的是：
                   1. 程序运行的结果可能超出整型的范围，所以要把f[]定义为long long类型；
                   2. 为了节省空间而省去了一维，第二重循环需要倒着写；
                   3. 最后求出的f[j]代表的是用1~n的数表示j的总方法数，所以最后的输出f[(n*n+n)/4]要除以2；
                   4. 程序最先判断所有数的和是否为偶数，第二重循环的最大值是和的一半。