1809.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:1809  User Id:fzk 
Memory:28K  Time:31MS
Language:C++  Result:Accepted

Source 

#include"stdio.h"

int x[4]={0,0,1,1},y[4]={0,1,0,1};
_int64 s[4],answer;

_int64 cc(int a,_int64 b)
{
 if(a>b)return 0;
  switch(a)
  {case 0:return 1;
   case 1:return b;
   case 2:return b*(b-1)/2;
   case 3:return b*(b-1)*(b-2)/3/2;
  }
  return 0;
}

void doit()
{answer=0;
int c[4]={0,0,0,0};
int i,j,k;

for(i=0;i<4;i++)
{c[i]++;
 for(j=i;j<4;j++)
 {c[j]++;
	for(k=j;k<4;k++)
	if(((x[i]+x[j]+x[k])*(y[i]+y[j]+y[k])+x[i]*y[i]+x[j]*y[j]+x[k]*y[k])%2==0)
	{c[k]++;
	 answer+=cc(c[0],s[0])*cc(c[1],s[1])*cc(c[2],s[2])*cc(c[3],s[3]);
	 c[k]--;
	}
  c[j]--;
 }
 c[i]--;
}

}


int main()
{long a,b;
int t,i,n,k;
scanf("%d",&t);
for(i=1;i<=t;i++)
{scanf("%d",&n);
 s[0]=s[1]=s[2]=s[3]=0;
 for(;n>0;n--)
 {scanf("%ld%ld",&a,&b);
 if(a<0)a=-a;if(b<0)b=-b;
 for(k=0;k<4;k++)if(a%2==x[k]&&b%2==y[k]){s[k]++;break;}
 }
 
 doit();
 printf("Scenario #%d:\n%I64d\n\n",i,answer);
}
return 0;
}