GCJ Japan 2011 Final B. Multiplication of Bacteria

Problem Description:
There are T standalone test cases in this problem.
In the beginning, there are A units of bacteria.
For any moment t with x units of bacteria, we know that moment t + 1 would have x**x units of bacteria.
Given A, B, C, you are interested at the number of units of bacteria at moment B, modulo C.

Constraints:
${1 ≤ T ≤ 500}$
${1 ≤ A, B, C ≤ 1000}$

Solution:
Let ${a_i}$ denote the number of units of bacteria at moment i.
Let ${b_{i, j}}$ denote ${a_i\ mod\ j}$ .
Essentially, we are interested at ${b_{B, C}}$ .
The transition can be derived by the following:
${b_{i, j} = (a_{i - 1}\ mod\ j)^{a_{i - 1}}\ mod\ j = b_{i - 1, j}^{a_{i - 1}}\ mod\ j}$
We know that under any equivalence system with some fixed modulo, the series ${v^0, v^1, v^2, ...}$ must form some cycle, and some non-negative length of head that precedes the entering of cycle.
We can precompute for each possible v and mod, and construct a table with each of the corresponding length of head and cycle.
With such values, by removing unnecessary loops, we can reduce the power in the previous equation to a computable extent.

Code:

#include <bits/stdc++.h>

const int MAXA = 1000;
const int MAXB = 1000;
const int MAXC = 1000;

int cyc[MAXC][MAXC + 1];
int hed[MAXC][MAXC + 1];
int nc[MAXA + 1][MAXB + 1];

int dp[MAXB + 1][MAXC + 1];

int int_pow(int v, int e, int m) {
  if (v == 0 || m == 1) return 0;
  int r = 1;
  for (int i = e; i; i >>= 1) {
    if (i & 1) (r *= v) %= m;
    (v *= v) %= m;
  }
  return r;
}

int naive_calc(int a, int b, int *nca) {
  if (b == 0) return nca[b] = a;
  int v = naive_calc(a, b - 1, nca);
  if (v == MAXC) return nca[b] = MAXC;
  int r = 1;
  for (int i = v; i; i >>= 1) {
    if (i & 1) r *= v;
    if (r > MAXC) return nca[b] = MAXC;
    v *= v;
    if (v > MAXC) return nca[b] = MAXC;
  }
  return nca[b] = r;
}

int solve(int a, int b, int c) {
  if (b == 0) return a % c;
  if (~dp[b][c]) return dp[b][c];
  int v = solve(a, b - 1, c);
  int e;
  if (nc[a][b - 1] >= hed[v][c]) {
    e = solve(a, b - 1, cyc[v][c]);
    e = (e - hed[v][c] % cyc[v][c] + cyc[v][c]) % cyc[v][c] + hed[v][c]; // ensure that it goes into the cycle, because it might get chopped of, e.g., head = 3, cycle = 5, solve = 5, then we will access some element that is not even in the cycle, obviously leading to something wrong
  } else {
    e = nc[a][b - 1];
  }
  return dp[b][c] = int_pow(v, e, c);
}

signed main() {
  for (int i = 0; i < MAXC; ++i) {
    for (int j = 1; j <= MAXC; ++j) {
      std::vector<int> vis(MAXC, -1);
      int ctr = 0;
      for (int u = 1; ; (u *= i) %= j) {
        if (~vis[u]) {
          cyc[i][j] = ctr - vis[u];
          hed[i][j] = vis[u];
          break;
        }
        vis[u] = ctr++;
      }
    }
  }
  for (int i = 1; i <= MAXA; ++i) {
    naive_calc(i, MAXB, nc[i]);
  }
  std::ios::sync_with_stdio(false);
  int T;
  std::cin >> T;
  for (int kase = 1; kase <= T; ++kase) {
    std::memset(dp, 0xff, sizeof(dp));
    int A, B, C;
    std::cin >> A >> B >> C;
    std::cout << "Case #" << kase << ": " << solve(A, B, C) << std::endl;
  }
  return 0;
}