TopCoderOpen 2015 Round1A Medium Autogame

無駄に手間のかかることをしてしまった。
http://community.topcoder.com/stat?c=problem_statement&pm=13707

問題

N頂点N有向辺からなるグラフが与えられる。
各辺の始点は、N個の頂点に1つずつある。

このN頂点のうち幾つかにコインを置く。
これらを有向辺に沿ってK回動かす、ということを行う。
その後、同じ頂点にコインが複数来ないようなコインの置き方は何通りあるか。

解法

まず各頂点に置いたコインがどれと重複しないか求める。
ダブリングを使ってK回コインを移動させても良いが、最終的に同じ頂点に来るコインはN回以内に同じ頂点に来るので、min(N,K)回実際にシミュレーションした方が楽だし早い。

min(N,K)回移動後、頂点xにコインが来るような初期位置の数をP(x)個とする。
これらP(x)個のうちに２つ以上コインを置くことはできないので、これらのP(x)個の頂点に対し、どれか１個コインを置くか全くコインを置かないので(P(x)+1)通りの置き方が考えられる。
この(P(x)+1)を全頂点xにおいて掛け合わせたものが解。

class Autogame {
	public:
	int wayscnt(vector <int> a, int K) {
		int N=a.size();
		int i,x,y,in[51]={};
		ll mo=1000000007;
		
		FOR(i,N) {
			y=i;
			FOR(x,min(K,50)) y=a[y]-1;
			in[y]++;
		}
		
		ll ret=1;
		FOR(i,N) ret=ret*(in[i]+1) % mo;
		return (int)ret;
	}
}

まとめ

最初無駄にダブリングしてしまった。