这题开始用深搜写，但是超时，无奈之下只好打表，交上看了一下别人的基本上都打得表
，做完之后又学习了一下大牛的深搜。
代码：
#include<stdio.h>
#define M 30
int n,sum,half ; // sum 记录一共有几种情况 half 代表可以安放的总数的一半
int num[M][M],res[M][M] ;// num[][] 记录放的情况，res[][] 存储前 x 个位置（已经安放的位置）
void dfs(int p) // 已经放了几个'+'（相当于动态规划的记忆化的数组）。
{
if(p>n)// 找到一种方案
{
sum++ ;
return ;
}
for(int i=0 ;i<2 ;i++) // 在第 p 个位置放'-'（1）或'-'（0）
{
int count=0 ; // count 记录一共有多少个‘+’
num[1][p]=i ; //把第一行放上'+'或'-'
count+=res[1][p-1]+i ;
for(int j=2 ;j<=p ;j++) // 依次递推计算出能推出来的
{
num[j][p-j+1]=num[j-1][p-j+1]^num[j-1][p-j+2] ;
if(num[j][p-j+1]) // 记录'+'的数量
count++ ;
}
res[1][p]=count ; // 记录已经安放的符号安放了几个'+'
if(count<=half&&p*(p+1)/2-count<=half) //已经安放的'+'或'-'的数量都不能超过总数的一半
dfs(p+1) ;
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
sum=half=0 ;
if((n*(n+1)/2)%2==0)
{
half=n*(n+1)/4 ;
dfs(1) ;
}
printf("%d\n",sum) ;
}
return 0 ;
}