TCO 2015 Round 1A Medium: Autogame (組み合わせ・シミュレーション)

問題

TopCoder Statistics - Problem Statement

解法

topcoder.g.hatena.ne.jp

最初に全てのマスにトークンを置いておき、収束するまで回す。 min(K, 50) 回だけ回せば良い。収束したら、マスにあるトークンの数+1を各マスについてかけ合わせる。

（収束後、あるマスiにn個トークンがある時、n個の別々のマスに置いても最終的にトークンがマスiに集まってしまうため、ゲームに負けないためにはそれらnこのマスのうち、トークンを置いて良いのは1つだけである。この時のトークンの置き方はn通りあるが、nこのマスのどこにもトークンを置かないという選択も可能なため、置き方はn+1とおりとなる。各マスに収束したトークンの数+1をかけ合わせると答えになるのは、このためである）

コード

import java.util.Arrays;

public class Autogame {

	public int wayscnt(int[] a, int K) {
		int N = a.length;
		int[] way = new int[N];
		Arrays.fill(way, 1);

		int[] nextway = new int[N];
		for (int i = 0; i < Math.min(K, 50); i++) {
			for (int j = 0; j < N; j++) {
				nextway[a[j] - 1] += way[j];
			}

			for (int j = 0; j < N; j++) {
				way[j] = nextway[j];
			}
			Arrays.fill(nextway, 0);
		}

		long ans = 1;
		for (int i = 0; i < N; i++) {
			ans *= way[i] + 1;
			ans %= 1000000007;
		}

		return (int) ans;
	}

}