hdu 2510 符号三角形

一道比较特殊的dfs题，同样给定了数据直接打表。

题目中的+和-的抵销规律可以看做0和1的异或运算，而且还有一个重要的规律，我不会证明那就是-的个数*2=总个数

还有就是这个回溯，真的是好长。。。。

打表代码，省去了freopen

#include <bits/stdc++.h>
using namespace std;
int ans[100];
int a[100][100];
int sum;
void dfs(int n)
{
  if(n>24)
  return;
  else
  {
    for(int i=0;i<=1;i++)
    {
      a[0][n]=i;
      sum+=i;
      for(int j=1;j<n;j++)
      {
        a[j][n-j]=a[j-1][n-j]^a[j-1][n-j+1];
        sum+=a[j][n-j];
      }
      if(sum*2==n*(n+1)/2)
      ans[n]++;
      dfs(n+1);
      sum-=i;
      for(int j=1;j<n;j++)
      {
        a[j][n-j]=a[j-1][n-j]^a[j-1][n-j+1];
        sum-=a[j][n-j];
      }
    }
  }
}
int main()
{
  dfs(1);
  int n;
  while(cin>>n)
  cout<<ans[n]<<endl;
}