Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-10-08Google Code Jam Japan 2011 決勝

Google Code Jam Japan 2011 決勝 B バクテリアの増殖

| 20:56 | Google Code Jam Japan 2011 決勝 B バクテリアの増殖 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 B バクテリアの増殖 - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 B バクテリアの増殖 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

A^A mod Cって普通にbinary methodで計算するだけでは?

全然違った。指数のほうはmod Cではダメらしい。

Aの2乗、3乗、4乗、、、と順番にmod Cで計算してみて、同じものが出てくるまでやってみる

Cが素数のときはC-1回で循環するはずである。Cが素数でないときでも鳩の巣原理でC-1回を超えることはない。

X回で循環したとすると、指数をX減らしても同じ結果になるということだから、指数はmod Xで計算すれば良いのか?

サンプルの最後が合わない。

指数の計算がA^A mod Xとかでやってたけどこれがだめっぽい気がする。指数の計算用の指数も考える必要が・・・?

・・・

1時間半も経った。無邪気にやりすぎた。

Aに浮気。

解いて戻ってきた。


smallなら解けるだろうか?A乗1回するだけなら本当にbinary methodするだけでは?

1WA。違った。A乗を最大2回だった。結局smallの何がLargeより簡単なんだろう。よく分からない。


再びLargeを考える。

指数の計算方法も同じである気がする。Aの2乗、3乗、、、と順番にmod Xで計算すると、どこかで循環する

循環の長さは当然Xより小さいはずだから、これを繰り返していけばいつかXが1になるはずだ

mod 1なら常にAは0になるので、ここで収束する

実装してみる

サンプル合った

WA。原因は想像がついている。

A mod Xを何乗かしたとき、必ずしもAに戻ってくるわけではない。例えばA^5=A^2だがA^4!=A^1みたいなのがあると、指数が2~5の間で循環するわけだから、必ずしも常にmodを取っていいわけではない。

うーーーーーん

時間切れ


以下終了後

実は2~5で循環する場合でも、2以上のXの場合は((X-2)%3+2)乗すれば良いわけだから、結局mod 3で見ればX%3と合同であることは変わらない

ってことは、最大でも1000乗すれば循環が始まっていると見て間違いないのだから、単に1000以上になる場合だけ、modで合同の1000以上の最小値を保持しておけば良いはずだ

書いてみた

small/largeともにPass

コンテスト終了後1時間以上も経っていた

もっと頭の回転早くないと無理だな


ソースコード

ll powgf(ll a, ll e, ll MOD) {
	if(a==0) return a;
	ll res=1;
	ll bias=999/MOD*MOD+MOD;
	for(; e; e>>=1) {
		if(e&1) res*=a;
		if(res>=bias) res=(res-bias)%MOD+bias;
		a=a*a;
		if(a>=bias) a=(a-bias)%MOD+bias;
	}

	return res;
}

int solve(int A, int B, int C) {
	int res=0;

	int cyc[1010];
	int i=C;
	while(i) {
		int x=A%i;
		int memo[1010];
		memset(memo, -1, sizeof(memo));
		memo[x]=0;
		while(memo[x*A%i]<0) {
			memo[x*A%i]=memo[x]+1;
			x=x*A%i;
		}
		cyc[i]=memo[x]+1-memo[x*A%i];
		if(i==cyc[i]) break;
		i=cyc[i];
	}

	int a[1010];
	for(int i=1; i<=C; i++) a[i]=A;
	for(int i=0; i<B; i++) {
		int j=C;
		while(j) {
			a[j]=powgf(a[j], a[cyc[j]]?a[cyc[j]]:cyc[j], j);
			if(j==cyc[j]) break;
			j=cyc[j];
		}
	}
	res=a[C]%C;
	return res;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		int A, B, C;
		ifs >> A >> B >> C;
		int res=solve(A, B, C);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}

NiiqiitoNiiqiito2013/02/17 11:57I hate my life but at least this makes it braeable.

xkhqsmsgifxkhqsmsgif2013/02/19 15:16E9CxwG <a href="http://cdmchajbiebt.com/">cdmchajbiebt</a>

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111008