poj 1186 方程的解数（HASH，DFS）

本文链接：https://blog.csdn.net/acm_cxq/article/details/52121481

方程的解数

Time Limit: 15000MS		Memory Limit: 128000K
Total Submissions: 7076		Accepted: 2428
Case Time Limit: 5000MS

Description

已知一个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)均为正整数。

Input

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

Output

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

Sample Input

Sample Output

题意：中文题不解释

思路：150*150*150是可以接受的，数组也是可以存下的，那么我们分成两部分去求即可

‘先求前面一半，用HASH保存下来，然后求后面一办，去找-sum有多少个即可

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define N 4000000
struct Node
{
    int a,b;
} p[10];
int n,m;
int ans,mid;
bool used[N];
struct Hash
{
    int val;
    int cnt;
} HashTable[N];
void initHash()
{
    memset(used,false,sizeof(used));
    memset(HashTable,0,sizeof(HashTable));
}
int SearchHash(int v)
{
    int temp = v;
    while(temp<0) 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 nn)
{
    int q=1;
    while(nn)
    {
        if(nn&1) q*=a;
        a*=a;
        nn>>=1;
    }
    return q;
}
void dfs(int d,int k)
{
    if(d>mid)
    {
        InsertHash(k);
        return;
    }
    for(int i=1; i<=m; i++)
        dfs(d+1,k+p[d].a*pow_(i,p[d].b));
}
void dfs1(int d,int k)
{
    if(d>n)
    {
        k=-k;
        int temp=SearchHash(k);
        if(HashTable[temp].val==k)
            ans+=HashTable[temp].cnt;
        return;
    }
    for(int i=1; i<=m; i++)
        dfs1(d+1,k+p[d].a*pow_(i,p[d].b));
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        initHash();
        ans=0;
        for(int i=1; i<=n; i++)
            scanf("%d %d",&p[i].a,&p[i].b);
        mid=n/2;
        dfs(1,0);
        dfs1(mid+1,0);
        printf("%d\n",ans);
    }
    return 0;
}

’