方程的解数

Time Limit: 15000MS		Memory Limit: 128000K
Total Submissions: 7045		Accepted: 2417
Case Time Limit: 5000MS

已知一个n元高次方程：


其中：x1, x2,...,xn是未知数，k1,k2,...,kn是系数，p1,p2,...pn是指数。且方程中的所有数均为整数。

假设未知数1 <= xi <= M, i=1,,,n，求这个方程的整数解的个数。

1 <= n <= 6；1 <= M <= 150。



方程的整数解的个数小于2³¹。

★本题中，指数Pi(i=1,2,...,n)均为正整数。

第1行包含一个整数n。第2行包含一个整数M。第3行到第n+2行，每行包含两个整数，分别表示ki和pi。两个整数之间用一个空格隔开。第3行的数据对应i=1，第n+2行的数据对应i=n。

仅一行，包含一个整数，表示方程的整数解的个数。

3

150

1  2

-1  2

1  2

178

由于6个数的搜索的层数最多会达到150^6..所以不可行，好的方法是将前3个数组合所有的解算出来并存入HASH表，然后算出后三个数的所有组合，每次对(-ans)进行查找，不过咏链式前向星构造的果断不行
看了别人的代码发现一个构造HASH表的很好的模板。

/*

6

150

1  2

-1  2

1  2

-1  2

1  2

-1  2

*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<math.h>

#include<queue>

#include<iostream>

using namespace std;

const int INF = ;

const int N = **;

int k[],p[];

int n,m,cnt,mid;

/*************构造HASH表****************/

bool used[N];

struct Hash{

    int val;

    int cnt;

}HashTable[N];

void initHash(){

    memset(used,false,sizeof(used));

    memset(HashTable,,sizeof(HashTable));

}

int SearchHash(int v)

{

    int temp = v;

    while(temp<) temp+=N;

    while(temp>=N) temp-=N;

    while(used[temp]&&HashTable[temp].val!=v){

        temp++;

        if(temp>=N) temp-=N;

     }

    return temp;

}

void InsertHash(int v)

{

    int pos = SearchHash(v);

    HashTable[pos].val = v;

    used[pos] = true;

    HashTable[pos].cnt++;

}

/*****************************************/

int pow(int a,int n)

{

    int ans = ;

    while(n)

    {

        if(n&) ans = ans*a;

        a = a*a;

        n>>=;

    }

    return ans;

}

void dfs(int step,int ans)

{

    if(step==mid)

    {

        InsertHash(ans);

        return ;

    }

    else

    {

        for(int i=; i<=m; i++)

        {

            dfs(step+,ans + k[step]*pow(i,p[step]));

        }

    }

}

void dfs2(int step,int ans)

{

    if(step==n+)

    {

        ans = -ans;

        int s = SearchHash(ans);

        if(HashTable[s].val == ans){

            cnt+=HashTable[s].cnt;

        }

        return ;

    }

    else

    {

        for(int i=; i<=m; i++)

        {

            dfs2(step+,ans + k[step]*pow(i,p[step]));

        }

    }

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        initHash();

        cnt = ;

        for(int i=; i<=n; i++)

        {

            scanf("%d%d",&k[i],&p[i]);

        }

        if(n==){

            printf("%d\n",);

            continue;

        }

        mid = n/+;

        dfs(,);

        dfs2(mid,);

        printf("%d\n",cnt);

    }

    return ;

}