|
|
题目链接：http://poj.org/problem?id=1186
  /**//*
 题意：
已知一个n元高次方程：
其中：x1, x2, ,xn是未知数，k1,k2,,kn是系数，p1,p2,pn是指数。
且方程中的所有数均为整数。
假设未知数1 <= xi <= M, i=1,,,n，求这个方程的整数解的个数。
1 <= n <= 6；1 <= M <= 150。
方程的整数解的个数小于2^31。
★本题中，指数Pi(i=1,2,,n)均为正整数。
题解：
DFS + HASH
思路：
一看到题目以为是解方程的，仔细一看，其实不然，题目有一个条件就是
未知数的数目n很小，只有6，而且未知数也是有上限（1 <= M <= 150），所以
当最大情况的时候可以枚举3个未知数的值，一共150^3，然后插入到hash表中，
再枚举另外三个组成的所有情况，每次得到一个和为S时，只要查询hash表中-S
的数的数量，加到最后的答案即可。
这样就把本来150^6的复杂度开了个根号。枚举数的时候因为n是不确定的
，所以我采用dfs来枚举，这样写起来会方便许多。
 */
#include <iostream>
using namespace std;
#define maxn 4642307
#define ll __int64
int split;
int nowPos[maxn], Case;
int hash[maxn];
int key[maxn];
int n, M;
int EXP(int a, int b) {
if(b == 0)
return 1;
int tmp = EXP(a*a, b/2);
if(b & 1)
tmp *= a;
return tmp;
}
struct point {
int k, p;
}pt[6];
void Insert(int val) {
int s = val % maxn;
if(s < 0)
s += maxn;
  while(1) {
if(nowPos[s] != Case) {
nowPos[s] = Case;
hash[s] = 1;
key[s] = val;
return ;
}else {
if(key[s] == val) {
hash[s] ++;
return ;
 }
s ++;
if(s == maxn)
s = 0;
}
}
}
int Query(int val) {
int s = val % maxn;
if(s < 0)
s += maxn;
while(1) {
if(nowPos[s] != Case) {
return 0;
}else {
if(key[s] == val) {
return hash[s];
}
s ++;
if(s == maxn)
s = 0;
}
}
}
void dfs0(int depth, int sum) {
if(depth == split || depth == n) {
Insert(sum);
return ;
}
int i;
for(i = 1; i <= M; i++) {
dfs0(depth+1, sum + pt[depth].k * EXP(i, pt[depth].p) );
}
}
void dfs1(int depth, int sum, int& ans) {
if(depth == n) {
ans += Query(- sum);
return ;
}
int i;
for(i = 1; i <= M; i++) {
dfs1(depth+1, sum + pt[depth].k * EXP(i, pt[depth].p), ans );
}
}
int main() {
int i;
while(scanf("%d %d", &n, &M) != EOF) {
if(n <= 4) {
split = 2;
}else
split = 3;
Case ++;
for(i = 0; i < n; i++) {
scanf("%d %d", &pt[i].k, &pt[i].p);
}
dfs0(0, 0);
int ans = 0;
if(n <= split) {
ans = Query(0);
}else {
dfs1(split, 0, ans);
}
printf("%d\n", ans);
}
return 0;
}
|