两数比较转化为自身属性
a,b互为完美对，即ai+bi=aj+bj,转化为ai-aj=-(bj-bi)
所以a,b互为完美对，等价于其差分序列相等。
注意：这里并不需要求出所有的ai-aj，因为有些ai-aj可以根据ai-aj=(ai-ak)+(ak-aj)推导出来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <iostream>
#include <vector>
#include <map>
using namespace std;
#define int long long
signed main() {
int n, k; cin >> n >> k;
int ans = 0;
map<vector<int>, int> mvii;
for(int i = 0; i < n; ++ i) {
vector<int> a(k);
for(int &t: a) cin >> t;
vector<int> b(k-1);
for(int j = 1; j < k; ++ j)
b[j-1] = a[j] - a[j-1];
ans += mvii[b];
for(int &t: b) t = -t;
mvii[b] ++;
}
cout << ans << endl;
}
|