kojingharangの日記

2015 TCO Round1A 500 Autogame

03:34 |

• N個の場所がありそれぞれにどこかの場所を指す矢印の根元がある。各場所に最大1個のトークンを置き一斉に矢印の通りに動かすのを K 回やる。
• 同じ場所にトークンが２つになってしまったら負け。負けないようなトークンの置き方は何通りあるか。mod 10^9+7で。
• 1≦N≦50, 1≦K≦10^9

• 全場所にトークンを置いたとして、K回動かしてトークンの位置を追跡する。
• 枝分かれしないので、１回合流したら合流しっぱなし。
• なので、最終的に場所が違う→独立に選べる
• 各場所について、最終的に集まったトークンの中から１個選ぶor0個選ぶ、ということで場所ごとに個数+1を掛ければよさげ。
• トークンIDの集合になるから vector<int> かとおもったけど単に個数でいいのだ。
• 最初 50 回くらいやれば収束するだろうからと 1000 回まわしたが K が小さいときもあるんだったということで min(K, 1000) に変更。あぶない。

• Accepted

class Autogame {
	public:
	int wayscnt(vector <int> a, int K) {
		int N=a.size();
		VI w(N);
		REP(i, N) w[i]=1;
		REP(loop, min(K, 1000)) {
			VI nw(N);
			REP(i, N) nw[a[i]-1]+=w[i];
			w = nw;
		}
//		cout<<w<<endl;
		ll ans=1;
		REP(i, N) {
			ans*=w[i]+1;
			ans %= 1000000007LL;
		}
		return ans;
	}
};

ツイートする