C++動的計画アルゴリズムのサブセットの和

サブセットの和
タイトルの説明
1からN(1<=N<=39)までの連続整数集合については、2つのサブ集合に分割することができ、各集合の数字の和が等しいことを保証することができる.
例えば、N=3の場合、{1,2,3}は2つのサブセットに分割され、それぞれのすべての数字は等しい:{3}and{1,2}これは唯一の分割法である(交換集合位置は同じ分割スキームと考えられるため、分割スキームの総数は増加しない)
N=7の場合,集合{1,2,3,4,5,6,7}を区別する4つの方法があり,各配布されたサブ集合の各数値和は,{1,6,7}と{2,3,4,5}1+6+7=2+3+4+5{2,5,7}と{1,3,4,6}と{1,2,5,6}{1,2,4,7}と{3,5,6}
Nを与えて、あなたのプログラムは分割スキームの総数を出力すべきで、このような分割スキームが存在しないならば、0を出力します.
入力
1行目:整数N
しゅつりょく
1行目:分割スキームの合計数を出力し、存在しない場合は0を出力します.
サンプル入力

7

サンプル出力

4 

コード#コード#
コードは次のとおりです.

#include<iostream>
using namespace std;
long long num[50][10000];
int n,QAQ;
main()
{
    cin>>n;
    QAQ=(n*(n+1))/2;
    if(QAQ%2)
    {
        cout<<"0"<<endl;
        return 0;
    }
    for(int i=1;i<=QAQ/2;i++) num[0][i]=0;
    for(int i=0;i<=n;i++) num[i][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=QAQ/2;j>=1;j--)
            num[i][j]=j>=i?num[i-1][j]+num[i-1][j-i]:num[i-1][j];
    cout<<num[n][QAQ/2]/2<<endl;
}