pku1186 方程的解数 (枚举加哈希)

题目:

题目是求一个n元高次方程的整数解的个数，中文题。注意到题目中的未知数个数最多有n(1<=n<=6)个，而且次数是输入的，直接求出每组解统计，显然是不行的。其中每个未知数最大可以为M(M<=150)，我们可以对每个未知数从1到M进行枚举，但这样的话，最坏情况下规模达到O(M^6)，显然会TLE。

因此我们要想办法缩小枚举范围，实际上我们只需枚举O（M^(n/2))的规模即可，比如n为6的话，我们枚举前3个未知数，将前3个未知数计算的和S1全部枚举出来，然后再枚举后3个未知数的和S2，如果S1=-S2的话，就表示有解。这样问题就转化为，当求出一个S2时，如何快速找出有没有相应的S1，以及S1出现了多少次的问题，相当于"快速找出某元素是在给定集合中"。这里我开始打算用MAP，但那样效率很低，因为要把相应的数字转化为字符串，于是改用哈希，哈希以前不太会，参考网上牛人的代码，写出本人第一个哈希。。。

my code:

 

#include<iostream>
using namespace std;
#define tmax 4000037
int hash[tmax],C[tmax];//hash表，C存的是相应S1出现的次数
bool use[tmax];//记录哈希表中某位置有没有用过
int k[6],p[6];//系数和次数
int n,M,ans,mid;
int locate(int s)//哈希表的定位函数
{
    int temp;
    temp=s;
    while(temp<0) temp+=tmax;
    while(temp>=tmax) temp-=tmax;
    while(use[temp]&&hash[temp]!=s)
    {
        temp++;
        if(temp>=tmax) temp-=tmax;
    }
    return temp;
}
void insert(int s)//哈希表的插入函数
{
    int pos=locate(s);
    hash[pos]=s;
    use[pos]=1;
    C[pos]++;
}
void lefthalf(int d,int s)//计算前一半的和S1，用递归避免嵌套循环
{
    int i,j,temp;
    if(d==mid)
    {
        insert(s);
        return ;
    }
    for(i=1;i<=M;i++)
    {    
        temp=k[d];
        if(temp!=0&&i!=1)
            for(j=0;j<p[d];j++) temp*=i;
        lefthalf(d+1,s+temp);
    }
}
void righthalf(int d,int s)//计算后一半的和S2，并统计解的个数
{
    int i,j,temp,pos;
    if(d==n)
    {
        s=-s;
        pos=locate(s);
        if(hash[pos]==s)
            ans+=C[pos];
        return ;
    }
    for(i=1;i<=M;i++)
    {
        temp=k[d];
        if(i!=1&&temp!=0)
            for(j=0;j<p[d];j++) temp*=i;
        righthalf(d+1,s+temp);
    }
}
int main()
{
    int i;
    cin>>n>>M;
    for(i=0;i<n;i++) cin>>k[i]>>p[i];
    mid=n/2;ans=0;
    lefthalf(0,0);
    righthalf(mid,0);
    cout<<ans<<endl;
    return 0;
}


练习哈希的好例子。。。