TopCoder SRM 728 Div2 Hard TrisomorphismEasy

Div2側は簡単。
https://community.topcoder.com/stat?c=problem_statement&pm=14808

問題

N頂点N辺の有向グラフが与えられる。
各頂点はそれぞれ出次数は1である。

各頂点には0～(N-1)のラベルが張られている。
3頂点を選び、ラベルをローテーションする、という処理を任意回数繰り返すとき、uniqueなグラフは何通りあるか。

解法

Nが小さいのでラベルの割り当てN!通り試せばよい。
ただし、この3頂点のラベルローテーションはラベル列の転送数の偶奇を変化させないので、N!通り中転送数の偶奇が変化する半分は無視しなければならない。
辺の集合を下手にvector等で持つとTLEスレスレなので、以下では1つの64bit整数型に押し込んだ。

class TrisomorphismEasy {
	public:
	int count(vector <int> E) {
		int N=E.size();
		vector<int> V;
		int x,y,i;
		ll p[11];
		
		p[0]=1;
		FOR(i,N) V.push_back(i), p[i+1]=p[i]*10;
		
		vector<ll> S;
		do {
			int rev=0;
			FOR(y,N) FOR(x,y) if(V[x]>V[y]) rev^=1;
			if(rev) continue;
			
			ll R=0;
			FOR(i,N) R+=V[E[i]]*p[V[i]];
			S.push_back(R);
			
		} while(next_permutation(ALL(V)));
		
		sort(ALL(S));
		return (unique(ALL(S))-S.begin())-1;
	}
}

まとめ

900pt～950ptでもいいかも。