TopCoder SRM 628 Div2 Hard InvariantSets

Div1 Mediumより難しかった。
http://community.topcoder.com/stat?c=problem_statement&pm=13242

問題

F[i]はN要素でかつ0～(N-1)の値を持つ数列である。

0～(N-1)の整数の部分集合であるEに対し、関数Fを適用すると集合EはE'=[x∈E:F[x]]に置き換えられる。
Fに対し、E'⊆EとなるようなEは何通りあるか。

解法

i→F[i]に辺を張ったグラフを考える。
ここでi∈Eなら、F[i]∈Eとならなければならない。

グラフ上で頂点iが閉路上にあるなら、頂点iをEに含むには閉路上の頂点全てを含まなければならない。
頂点iが閉路上にない場合、頂点iをEに含むにはi→F[i]→F[F[i]]→…の各頂点がすべてEに含まれなければならない。
各頂点は出次数が1なので、最終的にはどこかの閉路に落ち着く。

よって閉路上の各頂点から有向辺を逆向きにたどり、各枝におけるE候補の選び方を数え上げればよい。

class InvariantSets {
	public:
	vector <int> F;
	int inloop[51],vis[51],uf[51];
	vector<int> rev[51];
	int N;
	
	void dfs(int cur,int tar) {
		if(cur==tar) inloop[tar]=1;
		else if(!vis[cur]) vis[cur]++,dfs(F[cur],tar);
	}
	ll dfs2(int cur) {
		ll ret=1;
		int i;
		FOR(i,rev[cur].size()) ret*=1+dfs2(rev[cur][i]);
		return ret;
	}
	
	long long countSets(vector <int> f) {
		int i,x;
		F=f;
		N=f.size();
		ZERO(inloop);
		FOR(i,N) {
			ZERO(vis);
			dfs(f[i],i);
			uf[i]=i;
			if(inloop[i]) FOR(x,N) if(vis[x]) uf[i]=min(uf[i],x);
			rev[i].clear();
		}
		FOR(i,N) if(inloop[i]==0) rev[uf[f[i]]].push_back(i);
		ll ret=1;
		FOR(i,N) if(inloop[i] && uf[i]==i) ret*=1+dfs2(i);
		return ret;
	}
}

まとめ

SRM628で一番おもしろい問題だった。