# 11224: 【原1224】hash

### 题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1224

## Sample Input

``````6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
``````

## Sample Output

``````5
``````

## Limits

a,b,c,d的绝对值小于1000000，n小于500

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/5/29.
//

//
// Created by BugenZhao on 2019/5/29.
//

#ifndef SBL_BSEPARATECHAININGHASHST_H
#define SBL_BSEPARATECHAININGHASHST_H

template<typename Key, typename Value, typename Hasher>
class BSeparateChainingHashST {
static constexpr int INIT_CAPACITY = 4;

class Pair {
public:
Key key;
Value value;
};

class Node {
public:
Pair pair;
Node *next;

Node(const Pair &pair, Node *next = nullptr) : pair(pair), next(next) {}

Node() : next(nullptr) {}
};

int n;
int m;
Hasher hasher;
Node **st;

private:
int hash(const Key &key) {
return (hasher(key) & 0x7fffffff) % m;
}

public:
BSeparateChainingHashST() : BSeparateChainingHashST(INIT_CAPACITY) {}

BSeparateChainingHashST(int m) : m(m) {
n = 0;
st = new Node *[m]{};
}

virtual ~BSeparateChainingHashST() {
for (int i = 0; i < m; ++i) {
Node *p = st[i];
Node *q;
while (p) {
q = p->next;
delete p;
p = q;
}
}
delete[] st;
}

int size() {
return n;
}

bool isEmpty() {
return size() == 0;
}

bool contains(const Key &key) {
return get(key) != nullptr;
}

Pair *get(const Key &key) {
int i = hash(key);
Node *p = st[i];
while (p) {
if (p->pair.key == key) return &(p->pair);
p = p->next;
}
return nullptr;
}

void put(const Key &key, const Value &val) {
//        if (n >= 10 * m) resize(2 * m);

int i = hash(key);
Node *p = st[i];
while (p) {
if (p->pair.key == key) {
p->pair.value = val;
return;
}
p = p->next;
}
++n;
st[i] = new Node(Pair{key, val}, st[i]);
}

void increment(const Key &key) {
int i = hash(key);
Node *p = st[i];
while (p) {
if (p->pair.key == key) {
++p->pair.value;
return;
}
p = p->next;
}
++n;
st[i] = new Node(Pair{key, 1}, st[i]);
}

void remove(const Key &key) {
int i = hash(key);
Node *p = st[i];

if (st[i] == nullptr) return;

if (st[i]->pair.key == key) {
st[i] = st[i]->next;
delete p;
--n;
} else {
while (p->next) {
if (p->next->pair.key == key) {
auto q = p->next;
p->next = q->next;
delete q;
--n;
break;
}
p = p->next;
}
}
}

};

#endif //SBL_BSEPARATECHAININGHASHST_H

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll = long long;

struct hasher {
inline int operator()(int i) {
return i + 2000000;
}
};

int main() {
int n;
scanf("%d", &n);
auto a = new int[n];
auto b = new int[n];
auto c = new int[n];
auto d = new int[n];
for (int i = 0; i < n; ++i) {
scanf("%d%d%d%d", a + i, b + i, c + i, d + i);
}
BSeparateChainingHashST<int, int, hasher> st(4000001);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
st.increment(a[i] + b[j]);
}
}

ll ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
auto p = st.get(-c[i] - d[j]);
if (p) ans += p->value;
}
}

printf("%ld", ans);
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstring"
using namespace std;

constexpr int mod = 1000009;

class type {
public:
int key = -99999999;
int val = 0;
};

int val_data[509][4] = { 0 };
type hash_map[mod];

int get_pos(int key) {
int ans = (key + 2000009) % mod;
for (; hash_map[ans].key != key; ans = (ans + 1) % mod) {
if (hash_map[ans].key <= -99999999) {
hash_map[ans].key = key;
break;
}
}
return ans;
}

int main() {
int n;
scanf("%d", &n);

for (int i = 0; i < n; ++i) {
for (int j = 0; j < 4; ++j)
scanf("%d", &val_data[i][j]);
}

for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
++hash_map[get_pos(val_data[i][0] + val_data[j][1])].val;
}
}

int ans = 0;

for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ans += hash_map[get_pos(-val_data[i][2] - val_data[j][3])].val;
}
}

cout << ans;

return 0;
}
``````

## skyzh's solution

``````#include <iostream>
#include <cstring>

using namespace std;

unsigned alex_hash(long long i) {
return i;
}

bool equal(long long a, long long b) { return a == b; }

template<typename K, typename V>
struct HashMap {
struct Pair {
bool used;
K key;
V value;
} *data;
static const unsigned cap = 1048576;

HashMap() {
data = new Pair[cap];
memset(data, 0, sizeof(Pair) * cap);
}

V &visit(const K key) {
unsigned pos = alex_hash(key) % cap;
while (data[pos].used) {
if (equal(key, data[pos].key)) {
break;
}
++pos;
if (pos >= cap) pos = 0;
}
if (!data[pos].used) {
data[pos].used = true;
data[pos].key = key;
}
return data[pos].value;
}
};

HashMap<long long, int> hash_map;

const int MAX_SET = 500;

long long A[MAX_SET], B[MAX_SET], C[MAX_SET], D[MAX_SET];

int main() {
int N;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A[i] >> B[i] >> C[i] >> D[i];
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
++hash_map.visit(A[i] + B[j]);
}
}
long long ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
ans += hash_map.visit(- C[i] - D[j]);
}
}
cout << ans << endl;
return 0;
}
``````