Description
给你 \(n\) 个六元组，让你判断其中是否有两个六元组是同构的。
\(1\le n\le 10^5\)。
Solution
一个比较 Naive 的做法是直接对每个六元组内部从小到大排序，比如 4 3 2 1 6 5 排序后变为 1 2 3 4 5 6。如果两个六元组同构，那么此时排序后结果就是相同的，直接对新的六元组做哈希即可。
#include<bits/stdc++.h>
#define int long long
#define base 13331
using namespace std;
long long n,a[100005][10];
unsigned long long hsh[100005];
signed main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=6;j++){cin>>a[i][j];}sort(a[i]+1,a[i]+1+6);for(int j=1;j<=6;j++){hsh[i]=hsh[i]*base+a[i][j];}}sort(hsh+1,hsh+1+n);for(int i=2;i<=n;i++){if(hsh[i]==hsh[i-1]){cout<<"Twin snowflakes found."<<endl;return 0;}}cout<<"No two snowflakes are alike."<<endl;return 0;
}
如果这个题由六元组拓展到 \(k\) 元组，\(k\) 还非常大，我们 \(O(nk\log k)\) 的做法可能就寄了，因此考虑一些好玩的东西。
考虑设计一个 和组内元素次序无关，数值有关 的哈希函数 \(H(s)\)：
\[H(s)=(\sum_{i=1}^k s_i +\prod_{i=1} ^k s_i)\mod p
\]
其中 \(p\) 为某大质数，也可以直接自然溢出。
#include<bits/stdc++.h>
#define int long long
#define base 13331
using namespace std;
long long n,a[100005][10];
unsigned long long hsh[100005];
signed main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=6;j++){cin>>a[i][j];}hsh[i]=1;for(int j=1;j<=6;j++){hsh[i]*=a[i][j];}for(int j=1;j<=6;j++){hsh[i]+=a[i][j];}}sort(hsh+1,hsh+1+n);for(int i=2;i<=n;i++){if(hsh[i]==hsh[i-1]){cout<<"Twin snowflakes found."<<endl;return 0;}}cout<<"No two snowflakes are alike."<<endl;return 0;
}