Google Code Jam Japan 2011 Fianl B: バクテリアの増殖

GCJ

問題概要

X[0]=A(<1000), X[n+1] = X[n]^X[n]で定義される数列Xがある。X[B](B<=(small ? 2 : 1000))をmod C(<1000)で求める問題。

考えたこと

  • 全部mod Cでやるだけじゃダメなの？
  • ダメだ。指数の部分はmod Cだと値が変わる。
  • ということはX[i] mod Cの値だけ持っておいてもダメなのか。
  • 指数の部分もループに入るのでループの長さをLとするとX[i] mod Lの値も覚えておく必要がある。
  • でも、ループの長さってそれぞれ違うんだからLというよりL[ X[i] ]か。こんがらがる…。
  • とはいえだいぶ見えてきた。後はループの長さが分かれば良い。これは前処理でいけそう？後、ループに入るまでの長さと、ループの先頭の値もついでに計算しとこう。
  • それを持っておけば後は何とか書けそう。ループまで届かないときもあるが、それは超序盤に限る(X[i]<1000)ので、そのときは愚直にやろう。
  • 前処理はset使った手抜き実装でO(1000^3 * log 1000)。setのlogとはいえ1~2分あれば終わるだろう。
  • サンプルが思ってたより弱くて1WAもらったけど無事通った。いろんな値での剰余計算が出てきて混乱した。普段はひたすら%MODとつけるだけなので。
  • 冷静に考えるとsmallはちゃっちゃと書いて出しといた方が安全だった。

practiceで通ったコード

計算量は前処理O(MAX_C^3)(ただしこの実装では手抜きのためlogがくっつく)、その後はO(B*C*log C)。

#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
using namespace std;

const int MAX_C = 1000;
const int INF = 1<<29;

int A, B, C, NOW;
int L[MAX_C+1][MAX_C+1];
int TO[MAX_C+1][MAX_C+1];
int LOOP[MAX_C+1][MAX_C+1];
int X[MAX_C+1]; //現在値 % MOD
int Y[MAX_C+1]; //バッファ

int pow(int x, int k, int mod){
	if(x == 0){
		return 0;
	}
	int ret = 1, base = x;
	for(;k;k>>=1){
		if(k&1){
			ret = (ret * base) % mod;
		}
		base = (base * base) % mod;
	}

	return ret;
}

int solve(){
	if(C==1){
		return 0;
	}
	if(C==2){
		return A&1;
	}
	if(A==1){
		return 1;
	}

	for(int i=1; i<=C; i++){
		X[i] = A % i;
	}

	for(int i=0; i<B; i++){

		if(NOW < INF){
			for(int j=1; j<=C; j++){
				Y[j] = pow(X[j], NOW, j);
			}
		}
		else{
			for(int j=1; j<=C; j++){
				const int tar = TO[X[j]][j];
				const int mod = LOOP[tar][j];
				const int p = (( X[mod] - L[X[j]][j] - 1) % mod + mod ) % mod;

				Y[j] = (tar * pow(X[j], p , j)) % j;
			}
		}

		for(int j=1; j<=C; j++){
			X[j] = Y[j];
		}

		if(NOW == 2){
			NOW = 4;
		}
		else if(NOW == 3){
			NOW = 27;
		}
		else if(NOW == 4){
			NOW = 256;
		}
		else{
			NOW = INF;
		}

	}

	return X[C];
}

void pre_solve(){
	for(int mod=1; mod<=MAX_C; mod++){
		L[0][mod] = 0;
		TO[0][mod] = 0;
		LOOP[0][mod] = 1;
		for(int x=1; x<mod; x++){
			set<int> ss;
			vector<int> xs;
			int cur = x;

			for(int i=0; ; i++){
				if(!ss.insert(cur).second){
					int key = 0;
					for(key = 0; xs[key] != cur; key++);
					L[x][mod] = key;
					TO[x][mod] = cur;
					LOOP[x][mod] = i - key;
					break;
				}
				else{
					xs.push_back(cur);
					cur = ( cur * x ) % mod;
				}
			}

		}
	}
}

void initialize(){
	scanf("%d%d%d",&A,&B,&C);
	NOW = A;
}

int main(){
	int T;
	scanf("%d",&T);

	pre_solve();
	/*
	printf("TO[3][5] = %d\n", TO[3][5]);
	printf("TO[2][8] = %d\n", TO[2][8]);
	printf("L[2][8] = %d\n", L[2][8]);
	printf("LOOP[2][8] = %d\n", LOOP[2][8]);
	*/


	for(int c=1; c<=T; c++){
		initialize();
		printf("Case #%d: %d\n", c, solve());
	}

	return 0;
}

セットがあまりに重くて前処理に時間がかかりすぎるので、bool配列で高速化。

13a14
> bool visited[MAX_C+1];
95a97
> 			memset(visited, false, sizeof(visited));
97c99
< 				if(!ss.insert(cur).second){
---
> 				if(visited[cur]){
106a109
> 					visited[cur] = true;