題目：

對(duì)于從1到N (1 <= N <= 39) 的連續(xù)整數(shù)集合，能劃分成兩個(gè)子集合，且保證每個(gè)集合的數(shù)字和是相等的。舉個(gè)例子，如果N=3，對(duì)于{1，2，3}能劃分成兩個(gè)子集合，每個(gè)子集合的所有數(shù)字和是相等的：{3} 和 {1,2}這是唯一一種分法（交換集合位置被認(rèn)為是同一種劃分方案，因此不會(huì)增加劃分方案總數(shù)） 如果N=7，有四種方法能劃分集合{1，2，3，4，5，6，7}，每一種分法的子集合各數(shù)字和是相等的:{1,6,7} 和 {2,3,4,5} {注 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}給出N，你的程序應(yīng)該輸出劃分方案總數(shù)，如果不存在這樣的劃分方案，則輸出0。程序不能預(yù)存結(jié)果直接輸出（不能打表）。

輸入格式：

輸入文件只有一行，且只有一個(gè)整數(shù)N

輸出格式：

輸出劃分方案總數(shù)，如果不存在則輸出0。

樣例： SAMPLE INPUT

7

SAMPLE OUTPUT

4

思路:

動(dòng)態(tài)規(guī)劃: f[i][j]-選到第i個(gè)時(shí)集合一和為j的方案數(shù) f[i][j]+=f[i-1][j-i] for(i=2;i<=n;i++) for(j=g;j>=1;j- -) if(j>=i) f[i][j]=f[i-1][j-i]; 簡化得: f[i]+=f[i-j]

代碼: