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

解説読んでも分からなかった問題でしたが、再チャレンジしてみたら解けました。この問題は去年一番印象に残った問題の一つです。

問題概要

　あるバクテリアは、現在x個あったとすると１時間後にはx^x個に増えるという性質をもつ。もともとB個いたバクテリアがA時間後には何個になっているかを求めよ。ただし、とても大きな数なのでCで割った余りを求めよ。

1 ≦ A, B, C ≦ 1000

方針

　べき乗の部分は、先に余りを求めて計算してはいけないことに注意。Cが高々1000なので、鳩ノ巣原理によって任意の正の整数pのべき乗を並べたものは最高でも1000回以内にループに入る。ループに入るまでの長さと、ループの１サイクルの周期を予め計算しておく。あとはこの情報を利用して再帰的に解く。実装は結構ややこしかった。printfデバッグがうまくなった気がする。

ソースコード

const int MAX_N = 1000;
const long long INF = 10000;

int head[MAX_N+1][MAX_N+1];
int cycle[MAX_N+1][MAX_N+1];
int dp[MAX_N+1][MAX_N+1];
int val[MAX_N+1];

void init() {
    int used[MAX_N+1];
    for (int i = 1; i <= MAX_N; i++) {
        for (int j = 1; j <= MAX_N; j++) {
            memset(used, -1, sizeof(used));
            int p = 0;
            int x = 1;
            while (1) {
                x = x * i % j;
                if (used[x] >= 0) {
                    head[i][j] = used[x];
                    cycle[i][j] = p - used[x];
                    break;
                }
                used[x] = p++;
            }
        }
    }
    cerr << "init() done!" << endl;
}

long long power(long long x, long long b, long long mod) {
    long long ret = 1LL;

    while (b > 0) {
        if (b & 1)
            ret = ret * x % mod;
        x = x * x % mod;
        b >>= 1;
    }

    return ret;
}

long long power(long long x, long long b) {
    long long ret = 1LL;

    while (b > 0) {
        if (b & 1)
            ret = min(INF, ret*x);
        x = min(INF, x*x);
        b >>= 1;
    }

    return ret;
}

int rec(int x, int b, int mod) {
    if (!b) return x % mod;
    if (mod == 1) return 0;
    if (dp[b][mod] >= 0) return dp[b][mod];

    int y = rec(x, b-1, mod);
    if (!y)
        return dp[b][mod] = 0;

    int p = head[y][mod];
    int q = cycle[y][mod];

    int ret;
    if (val[b-1] <= p)
        ret = power(y, val[b-1], mod);
    else {
        int z = rec(x, b-1, q);
        z = ((z - (p+1)) % q + q) % q + 1;
        ret = power(y, p+z, mod);
    }

    return dp[b][mod] = ret;
}

void solve() {
    int T;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cerr << "solving case " << i+1 << endl;
        int A, B, C;
        cin >> A >> B >> C;

        val[0] = A;
        for (int j = 1; j <= MAX_N; j++)
            val[j] = power(val[j-1], val[j-1]);

        memset(dp, -1, sizeof(dp));
        int ret = rec(A, B, C);
        cout << "Case #" << i+1 << ": " << ret << endl;
    }
}

#define SUBMIT
int main() {
#ifdef SUBMIT
    freopen("./test.in", "r", stdin);
    freopen("./test.out", "w", stdout);
#endif

    init();
    solve();

#ifdef SUBMIT
    fflush(stdout);
    cerr << "all done!" << endl;
#endif
    return 0;
}