# 14322: 【原4322】完美对

### 题目描述

author: smallling 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4322

## Input Format

$1 \leq n \leq 10^5, 2 \leq k \leq 10, 1 \leq a_i \leq 100$

## Sample Input

5 3
2 11 21
19 10 1
20 11 1
6 15 24
18 27 36


## Sample Output

3


## ligongzzz's solution

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
using ull = unsigned long long;
constexpr auto mod = 203ull;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n, k;
cin >> n >> k;

unordered_map<ull, int> rdata, ldata;
int zero_num = 0;

for (int i = 0; i < n; ++i) {
ull rcode = 0ull, lcode = 0ull;
int fnum;
cin >> fnum;
for (int j = 1; j < k; ++j) {
int tmp;
cin >> tmp;
rcode = rcode * mod + ull(100 + tmp - fnum);
lcode = lcode * mod + ull(100 + fnum - tmp);
}
if (rcode == lcode) {
zero_num++;
continue;
}

if (rdata.find(rcode) == rdata.end()) {
rdata[rcode] = 1;
}
else
{
rdata[rcode]++;
}

if (ldata.find(lcode) == ldata.end()) {
ldata[lcode] = 1;
}
else
{
ldata[lcode]++;
}
}

int ans = 0;
for (auto p : rdata) {
if (ldata.find(p.first) != ldata.end()) {
ans += p.second * ldata[p.first];
}
}
ans /= 2;
ans += zero_num * (zero_num - 1) / 2;

cout << ans;

return 0;
}


## zqy2018's solution

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, k, a[100005][11];
map<vector<int>, int> mp;
void init(){
REP(i, 1, n)
REP(j, 1, k)
}
void solve(){
ll ans = 0;
vector<int> tmp(11, 0);
REP(i, 1, n){
REP(j, 1, k - 1)
tmp[j] = a[i][j + 1] - a[i][1];
if (mp.count(tmp))
ans += mp[tmp];
REP(j, 1, k - 1)
tmp[j] = a[i][1] - a[i][j + 1];
if (!mp.count(tmp))
mp[tmp] = 0;
++mp[tmp];
}
printf("%lld\n", ans);
}
int main(){
init();
solve();
return 0;
}