1372.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1372 on 2006-01-19 at 14:14:26 */ 
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

typedef long long int64;
typedef unsigned int uint;
const int HASH_LIMIT = 3999971;
const int HASH_MAX = 4194304;
const int MAX = 160;
const int L_MAX = 32;

class HashTable {
private:
	int table[HASH_MAX], num[HASH_MAX];
public:
	static int hash(const int);
	void clear();
	void insert(const int);
	int find(const int);
};
int HashTable::hash(const int n) {
	return abs(n % HASH_LIMIT);
}
void HashTable::clear() {
	memset(table, -1, sizeof(table));
}
void HashTable::insert(const int n) {
	int index;
	for(index = HashTable::hash(n); table[index] != -1; index++) {
		if(index >= HASH_LIMIT) index -= HASH_LIMIT;
		if(table[index] == n) {
			num[index]++;
			return;
		}
	}
	table[index] = n; num[index] = 1;
}

int HashTable::find(const int n) {
	int index;
	for(index = HashTable::hash(n); table[index] != -1; index++) {
		if(index >= HASH_LIMIT) index -= HASH_LIMIT;
		if(table[index] == n) return num[index];
	}
	return 0;
}

int f[MAX][L_MAX], fn[MAX] = { 0 };
int p[8], k[8];
int n, M, slove;
HashTable ht;

inline int64 mabs(int64);
void enumer(int, int64);
void finder(int, int64);

int main()
{
	int i, j;

	for(i = 1; i < MAX; i++) {
		int64 r = 1;
		for(j = 0; j < L_MAX && r < INT_MAX; j++) {
			f[i][j] = r;
			fn[i]++;
			r *= i;
		}
	}
	while(scanf("%d %d", &n, &M) != EOF) {
		ht.clear(); slove = 0;
		for(i = 0; i < n; i++) scanf("%d %d", &k[i], &p[i]);
		enumer(0, 0);
		finder((n+1)/2, 0);
		printf("%d\n", slove);
	}
	
	return 0;
}

inline int64 mabs(int64 n)
{
	return n > 0 ? n : -n;
}
void enumer(int m, int64 prev)
{
	int i;
	if(mabs(prev) < INT_MAX) {
		if(m == (n+1)/2) ht.insert(prev);
		else {
			for(i = M; p[m] < fn[i]; i--)
				enumer(m+1, prev+k[m]*f[i][p[m]]);
		}
	}
}
void finder(int m, int64 prev)
{
	int i;
	if(mabs(prev) < INT_MAX) {
		if(m == n) slove += ht.find(-prev);
		else {
			for(i = M; p[m] < fn[i]; i--)
				finder(m+1, prev+k[m]*f[i][p[m]]);
		}
	}
}