学步园

这... 练练搜索吧... 自己写的哈希都不行.. 悲催悲催...

/********************
HDU 4277
Sevenster
2012.09.12
********************/
#include<iostream>
#include<algorithm>
#include<set>
#include<cmath>
#define HashSize (1<<15)-1;
using namespace std;

int T,N,ans,sum;
int E[16];
__int64 hash[1<<15];
set<__int64>se;

bool judge( int a,int b,int c )
{
 	 if( a+b>c&&abs(a-b)<c )
 	 	 return true;
 	 return false;
}

void swap( int &a,int &b )
{
 	 a^=b;b^=a;a^=b;
}

bool Hash( int a,int b,int c )
{
 	 if( a<b ) swap(a,b);
 	 if( b<c ) swap(b,c);
 	 if( a<b ) swap(a,b);
 	 __int64 ploy=a+b*sum+c*sum*sum;
 	 if( se.find(ploy)==se.end() )
 	 {	 
   	 	 se.insert(ploy);
 	 	 return true;
	 }
	 return false;
 	 /**
 	 int val=ploy%HashSize;
 	 while( hash[val]!=-1||hash[val]!=ploy )
 	 		val=(val<<1|1)%HashSize;
 	 if( hash[val]==-1 )
 	 {
 	 	 hash[val]=ploy;
 	 	 return true;
	 }*/
}

void dfs( int a,int b,int c,int d )
{
	 if( judge(a,b,c)&&Hash(a,b,c) )
  	 	 ans++;
 	 if( d>N )
	  	 return ;
 	 if( c-E[d]+b>a+E[d] )
 	 	 dfs( a+E[d],b,c-E[d],d+1 );
	 if( c-E[d]+a>b+E[d] )
 	 	 dfs( a,b+E[d],c-E[d],d+1 );
  	 dfs( a,b,c,d+1 );
}
 	
int main()
{
 	scanf( "%d",&T );
 	while( T-- )
 	{
	 	   ans=0;
	 	   se.clear();
	 	   memset( hash,-1,sizeof(hash) );
	 	   scanf( "%d",&N );
	 	   sum=0;
	 	   for( int i=1;i<=N;i++ )
	 	   {
	 	   		scanf( "%d",&E[i] );
	 	   		sum+=E[i];
		   }
	 	   dfs( E[1],0,sum-E[1],2 );
	 	   printf( "%d\n",ans );
  	}
 	return 0;
}