给出n个环状六元组({a_1,a_2,a_3,a_4,a_5,a_6})。询问里面是否有两个相同的六元组，(nleq 100000)。
解
思考到用hash来离散化，问题在于对环的处理，不妨让六元组元的下标从0开始，因为这样便于模表现环，设hash函数(H(a_0,a_1,a_2,a_3,a_4,a_5)=sum_{i=0}^5a_i+prod_{i=0}^5a_i)。
对于两个相同的hash值，拆环成链，枚举链的起点，注意除了顺时针枚举，还要逆时针枚举（画张图就清楚了），枚举的时候利用模实现模拟环（具体看代码）。
参考代码：
未封装
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define ll long long
#define gzy 526619
using namespace std;
struct snowflake{
int a[6];
}hl;
struct data{
data*next;snowflake d;
}*head[gzy],*pt;
il void read(int&);
il int Hash(snowflake&);
il bool insert(snowflake&),
equal(snowflake&,snowflake&);
int main(){
int n;read(n);
for(int i(1),j;i<=n;++i){
for(j=0;j<6;++j)
read(hl.a[j]);
if(insert(hl))
return puts("Twin snowflakes found."),0;
}puts("No two snowflakes are alike.");
return 0;
}
il int Hash(snowflake&x){int ans(1);
for(ri int i(0);i<6;++i)
ans=(ll)x.a[i]*ans%gzy;
for(ri int i(0);i<6;++i)
ans=(ans+x.a[i])%gzy;
return ans;
}
il bool equal(snowflake &a,snowflake &b){
for(ri int i(0),j,k;i<6;++i)
for(j=0;j<6;++j){
for(k=0;k<6;++k)
if(a.a[(i+k)%6]!=b.a[(j+k)%6])break;
if(k==6)return true;
for(k=0;k<6;++k)
if(a.a[(i+k)%6]!=b.a[(j-k+6)%6])break;
if(k==6)return true;
}return false;
}
il bool insert(snowflake&x){int H(Hash(x));
for(pt=head[H];pt!=NULL;pt=pt->next)
if(equal(x,pt->d))return true;
pt=new data,pt->next=head[H],head[H]=pt;
return pt->d=x,false;
}
il void read(int &x){
x^=x;ri char c;while(c=getchar(),c<'0'||c>'9');
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
封装
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define ll long long
#define gzy 491039
using namespace std;
il void read(int&);
template<class free>
struct unordered_map{
struct data{
data*next;free v;
}*head[gzy],*pt;
il void insert(free x){
ri int key(x%gzy);
pt=new data,pt->v=x;
pt->next=head[key];
head[key]=pt;
}
il data* find(free x){
for(pt=head[x%gzy];pt!=NULL;pt=pt->next)
if(pt->v==x)return pt;return NULL;
}
};
struct snow{
int a[6];
il int operator%(int psj){int ans(1);
for(ri int i(0);i<6;++i)
ans=(ll)ans*a[i]%psj;
for(ri int i(0);i<6;++i)
ans=(ans+a[i])%gzy;
return ans;
}
il bool operator==(snow x){
ri int i,j,k;
for(i=0;i<6;++i)
for(j=0;j<6;++j){
for(k=0;k<6;++k)
if(a[(i+k)%6]!=x.a[(j+k)%6])break;
if(k==6)return true;
for(k=0;k<6;++k)
if(a[(i-k+6)%6]!=x.a[(j+k)%6])break;
if(k==6)return true;
}return false;
}
il void read(){
for(ri int i(0);i<6;++i)::read(a[i]);
}
}hl;unordered_map<snow>U;
int main(){
int n;read(n);
for(int i(1);i<=n;++i){
hl.read();
if(U.find(hl)==NULL)U.insert(hl);
else return puts("Twin snowflakes found."),0;
}puts("No two snowflakes are alike.");
return 0;
}
il void read(int &x){
x^=x;ri char c;while(c=getchar(),c<'0'||c>'9');
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}