1.0-1背包求方案数
题目描述：
对于由从1到N (1 <= N <= 39)这N个连续的整数组成的集合来说，我们有时可以将集合分成两个部分和相同的子集合。
例如，N=3时，可以将集合{1, 2, 3} 分为{1,2}和{3}。此时称有一种方式（即与顺序无关）。
N=7时，共有四种方式可以将集合{1, 2, 3, ..., 7} 分为两个部分和相同的子集合：
{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。
输出：方式数。若不存在这样的拆分，则输出0

样例.png

思路：把和的一半作为背包大小，最后拆分方案=背包数/2
代码如下：

//锅在long long int上 
#include<cstdio>
using namespace std;
long long int dp[1000];
int a[100];
long long int solve(int n)
{
    int sum=0;
    for(int i=0;i<=n;i++)
    {
        a[i]=i;
        sum+=i;
    }
    if(sum%2)
      return 0;
    sum/=2;
    dp[0]=1;
    for(int i=1;i<=n;i++)
      for(int j=sum;j>=a[i];j--)
           dp[j]+=dp[j-a[i]];
    if(dp[sum]%2)
      return 0;
    else
      return dp[sum]/2;
}
int main()
{
    int n;
    scanf("%d",&n);
    long long ans=solve(n);
    printf("%lld\n",ans);
    return 0;
    
}

涉及的知识点：
1.二维转一维
一个很好的解释：https://blog.csdn.net/sunshine_lyn/article/details/79482477
2.恰好装满
3.求方案数

踩坑点：
没注意到数据范围，要用long long int