|
|
題目鏈接：http://poj.org/problem?id=1186
  /**//*
 題意：
已知一個n元高次方程：
其中：x1, x2, ,xn是未知數(shù)，k1,k2,,kn是系數(shù)，p1,p2,pn是指數(shù)。
且方程中的所有數(shù)均為整數(shù)。
假設(shè)未知數(shù)1 <= xi <= M, i=1,,,n，求這個方程的整數(shù)解的個數(shù)。
1 <= n <= 6；1 <= M <= 150。
方程的整數(shù)解的個數(shù)小于2^31。
★本題中，指數(shù)Pi(i=1,2,,n)均為正整數(shù)。
題解：
DFS + HASH
思路：
一看到題目以為是解方程的，仔細(xì)一看，其實不然，題目有一個條件就是
未知數(shù)的數(shù)目n很小，只有6，而且未知數(shù)也是有上限（1 <= M <= 150），所以
當(dāng)最大情況的時候可以枚舉3個未知數(shù)的值，一共150^3，然后插入到hash表中，
再枚舉另外三個組成的所有情況，每次得到一個和為S時，只要查詢hash表中-S
的數(shù)的數(shù)量，加到最后的答案即可。
這樣就把本來150^6的復(fù)雜度開了個根號。枚舉數(shù)的時候因為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;
}
|