Submission #1658805

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
typedef long long LL;
const int N=1e5;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
const int mo=1e7+9;
int head[mo],nxt[N],w[N],v[N],tot;LL to[N];
int c[N][4];
//有旋转同构，我们强制其中标号最小的方块向前方正方
//然后枚举最小的方块和最小的方块相对的方块，这样每个方块的四个角的颜色都确定了，用哈希求剩下四个面的方案数即可
//有个小trick，四个角的颜色可能有循环节，注意到哈希值相同的方块循环节也一定相同，所以求值时同时乘上循环节大小
inline void ins(LL s,int t) {
	int h=s%mo;
	for (int i=head[h];i;i=nxt[i])
		if (to[i]==s) { w[i]+=t; return; }
	to[++tot]=s,nxt[tot]=head[h],head[h]=tot,w[tot]=t;
	v[tot]=s%1000000==s/1000000?(s%1000==s/1000000000?4:2):1;
}
inline int find(LL s) {
	for (int i=head[s%mo];i;i=nxt[i])
		if (to[i]==s) return w[i]*v[i];
	return 0;
}
inline LL get(int k,int t) { LL s=0; for (int i=0;i<4;i++) s=s*1000+c[k][(t+i)&3]; return s; }
inline void Add(LL s,int t) {
	LL p[4];
	for (int i=0;i<4;i++) p[i]=s,s=s/1000+s%1000*1000000000;
	sort(p,p+4);
	for (int i=0;i<4;i++) if (!i||p[i]!=p[i-1]) ins(p[i],t);
}
inline void add(int k,int t) { Add(get(k,0),t); }
int main()
{
	int n=gi(),i,j,k,t;LL s,ans=0,pi;
	for (i=0;i<n;add(i++,1))
		for (j=0;j<4;j++)
			c[i][j]=gi();
	for (i=0;i<n;i++) {
		add(i,-1);
		for (j=i+1;j<n;j++) {
			add(j,-1);
			reverse(c[j],c[j]+4);
			for (k=0;k<4;k++) {
				pi=1;
				for (t=0;t<4;t++) {
					s=((c[j][(k+t)&3]*1000LL+c[j][(k+t+1)&3])*1000+c[i][(t+1)&3])*1000+c[i][t];
					pi*=find(s);
					if (!pi) break;
					Add(s,-1);
				}
				while (t--) {
					s=((c[j][(k+t)&3]*1000LL+c[j][(k+t+1)&3])*1000+c[i][(t+1)&3])*1000+c[i][t];
					Add(s,1);
				}
				ans+=pi;
			}
			reverse(c[j],c[j]+4);
			add(j,1);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result