符号三角.cpp

对于符号三角形问题

#include"iostream.h"
class Triangles  
{
public:
Triangles();
virtual ~Triangles();
long Compute(int); 
private:
void Backtrack(int t);
int n,half,count,**p;
long sum;
};
Triangles::Triangles()
{

}

Triangles::~Triangles()
{

}

void Triangles::Backtrack(int t)
{
	int i=0,j=0;
if((count>half)||(t*(t-1)/2-count>half)) return;
if(t>n)sum++;
else
   for(i=0;i<2;i++)
   {
    p[1][t]=i;
    count+=i;
    for(j=2;j<=t;j++)
    {
     p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];
     count+=p[j][t-j+1];
    }

    Backtrack(t+1);
    for( j=2;j<=t;j++)
     count-=p[j][t-j+1];
    count-=i;
   }
}

long Triangles::Compute(int n)
{
Triangles x;
int i;
int **p;
x.n=n;
x.count=0;
x.sum=0;
x.half=n*(n+1)/2;
if(x.half%2==1)return 0;
x.half=x.half/2;
p=new int *[n+1];

for(i=0;i<=n;i++)
   p[i]=new int[n+1];

for( i=0;i<=n;i++)
   for(int j=0;j<=n;j++)
    p[i][j]=0;
   x.p=p;
   x.Backtrack(1);
   delete[]p;
  
return x.sum;
}
int main(int argc, char* argv[])
{     Triangles t;
     int n[1000],i=0;
	 i=1;
	 cin>>n[i];
	 while(n[i]!=0)
	 {
		 ++i;
	   cin>>n[i];
	 }
	 i=1;
	 while(n[i]!=0)
	 { 
       cout<<t.Compute(n[i])<<endl;
	   ++i;
	 }
return 0;
}