1186.txt

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

 

#include"iostream.h"
#include"memory.h"
const long prime=3111011;
const long big=2147483647;

long answer;
long hash[prime];
int num[prime];
long mi[151][32];

long find(long m)
{long n=unsigned long(m)%prime;
while(num[n]&&hash[n]!=m){n=(n+1)%prime;}
return n;}
int h,m,*k,*p;

void qiu(int a,long s)
{long t,e;int i;
for(i=1;i<=m;i++)
{t=k[a]*mi[i][p[a]]+s;
 if(a+1==h){e=find(t);
	if(!num[e]){hash[e]=t;num[e]=1;}
	else num[e]++;
		}
else qiu(a+1,t);
}
}

void jie(int a,long s)
{long t,e;int i;
for(i=1;i<=m;i++)
{t=k[a]*mi[i][p[a]]+s;
 if(a+1==h){e=find(-t);answer+=num[e];}
 else jie(a+1,t);
 }
} 

int main()
{int n,nk[6],np[6],i,a,t,zh,fu,z_n,nn;long key;

cin>>n>>m;
key=1;fu=0;zh=0;z_n=0;nn=0;

for(i=0;i<n;i++)
{cin>>a;
if(a==0){key*=m;z_n++;cin>>a;}
else {nk[nn]=a;cin>>np[nn++];
		if(a>0)zh++;else fu++;}
}
if(fu==0||zh==0){if(z_n==n)cout<<key<<endl;else cout<<0<<endl;return 0;}

for(i=1;i<=m;i++)
{t=2;mi[i][1]=i;
while(t<32&&mi[i][t-1]<=big/i){mi[i][t]=mi[i][t-1]*i;t++;}
}
memset(num,0,prime*sizeof(int));

k=nk;p=np;h=nn/2;
qiu(0,0);

k=nk+h;p=np+h;h=nn-h;answer=0;
jie(0,0);

cout<<key*answer<<endl;
return 0;
}