poj 1186 方程的解数

#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>using namespace std;const int MAX = 4000000;bool used[MAX] = {0};int ki[7], pi[7];struct Hash{    int val;    int count;};Hash HashTable[MAX];int n, m, ans, mid;int getpow(int x, int p) {    int tmp = 1;    while (p) {        if (p&1) tmp *= x;        x *= x;        p >>= 1;    }    return tmp;}int searchHash(int s) {    int tmp;    tmp = s;    while (tmp < 0) tmp += MAX;    while (tmp >= MAX) tmp -= MAX;    while (used[tmp] && HashTable[tmp].val != s) {        tmp++;        if (tmp >= MAX) tmp -= MAX;    }    return tmp;}void insert(int s) {    int pos = searchHash(s);    HashTable[pos].val = s;    used[pos] = 1;    HashTable[pos].count++;}void leftHalf(int k, int s) {    int i;    if (k == mid) {        insert(s);        return;    }    for (i = 1; i <= m; ++i) {        leftHalf(k+1,s+ ki[k]*getpow(i, pi[k]));    }}void rightHalf(int k, int s) {    int i, pos;    if (k == n) {        s = -s;        pos = searchHash(s);        if (HashTable[pos].val == s) ans += HashTable[pos].count;        return;    }    for (i = 1; i <= m; ++i) {        rightHalf(k+1,s+ki[k]*getpow(i, pi[k]));    }}int main(){    scanf("%d", &n);    scanf("%d", &m);    int i;    ans = 0;    mid = n/2;    for (i = 0; i < n; ++i)        scanf("%d %d", &ki[i], π[i]);    leftHalf(0, 0);    rightHalf(mid, 0);    printf("%dn", ans);    return 0;}