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

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

問題概要

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

1 ≦ A, B, C ≦ 1000

方針

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

ソースコード

view plainprint?

1. const int MAX_N = 1000;  
2. const long long INF = 10000;  
3.   
4. int head[MAX_N+1][MAX_N+1];  
5. int cycle[MAX_N+1][MAX_N+1];  
6. int dp[MAX_N+1][MAX_N+1];  
7. int val[MAX_N+1];  
8.   
9. void init() {  
10.     int used[MAX_N+1];  
11.     for (int i = 1; i <= MAX_N; i++) {  
12.         for (int j = 1; j <= MAX_N; j++) {  
13.             memset(used, -1, sizeof(used));  
14.             int p = 0;  
15.             int x = 1;  
16.             while (1) {  
17.                 x = x * i % j;  
18.                 if (used[x] >= 0) {  
19.                     head[i][j] = used[x];  
20.                     cycle[i][j] = p - used[x];  
21.                     break;  
22.                 }  
23.                 used[x] = p++;  
24.             }  
25.         }  
26.     }  
27.     cerr << "init() done!" << endl;  
28. }  
29.   
30. long long power(long long x, long long b, long long mod) {  
31.     long long ret = 1LL;  
32.   
33.     while (b > 0) {  
34.         if (b & 1)  
35.             ret = ret * x % mod;  
36.         x = x * x % mod;  
37.         b >>= 1;  
38.     }  
39.   
40.     return ret;  
41. }  
42.   
43. long long power(long long x, long long b) {  
44.     long long ret = 1LL;  
45.   
46.     while (b > 0) {  
47.         if (b & 1)  
48.             ret = min(INF, ret*x);  
49.         x = min(INF, x*x);  
50.         b >>= 1;  
51.     }  
52.   
53.     return ret;  
54. }  
55.   
56. int rec(int x, int b, int mod) {  
57.     if (!b) return x % mod;  
58.     if (mod == 1) return 0;  
59.     if (dp[b][mod] >= 0) return dp[b][mod];  
60.   
61.     int y = rec(x, b-1, mod);  
62.     if (!y)  
63.         return dp[b][mod] = 0;  
64.   
65.     int p = head[y][mod];  
66.     int q = cycle[y][mod];  
67.   
68.     int ret;  
69.     if (val[b-1] <= p)  
70.         ret = power(y, val[b-1], mod);  
71.     else {  
72.         int z = rec(x, b-1, q);  
73.         z = ((z - (p+1)) % q + q) % q + 1;  
74.         ret = power(y, p+z, mod);  
75.     }  
76.   
77.     return dp[b][mod] = ret;  
78. }  
79.   
80. void solve() {  
81.     int T;  
82.   
83.     cin >> T;  
84.     for (int i = 0; i < T; i++) {  
85.         cerr << "solving case " << i+1 << endl;  
86.         int A, B, C;  
87.         cin >> A >> B >> C;  
88.   
89.         val[0] = A;  
90.         for (int j = 1; j <= MAX_N; j++)  
91.             val[j] = power(val[j-1], val[j-1]);  
92.   
93.         memset(dp, -1, sizeof(dp));  
94.         int ret = rec(A, B, C);  
95.         cout << "Case #" << i+1 << ": " << ret << endl;  
96.     }  
97. }  
98.   
99. #define SUBMIT  
100. int main() {  
101. #ifdef SUBMIT  
102.     freopen("./test.in", "r", stdin);  
103.     freopen("./test.out", "w", stdout);  
104. #endif  
105.   
106.     init();  
107.     solve();  
108.   
109. #ifdef SUBMIT  
110.     fflush(stdout);  
111.     cerr << "all done!" << endl;  
112. #endif  
113.     return 0;  
114. }  

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;
}