Internet Problem Solving Contest

• Correct output – H1
• Correct output – H2
• C++ program solving both data sets
• bc program solving both data sets

The most simple way how to compute the output was to simulate the bacteria expansion step-by-step. If your programming language doesn't support long numbers, you had to implement some simple arithmetical operations with them on your own. This solution worked for the easy input file. Unfortunately, it is too slow to solve the hard input.

Yes, but is there a way to do something better than a plain simulation? Let's imagine the array of colonies as a vector. Each of the changes that could be applied to the colonies is in fact some linear transformation. We may describe each of the operations using a square (NxN) matrix. To apply the change now means to multiply the vector containing the numbers of bacteria by the corresponding matrix.

If you don't understand the terms vector and matrix, please consult some book on basic algebra or an online resource such as MathWorld. The only things you need to know for the purpose of this task are: what is a vector, what is a matrix and how to multiply them. If you do understand these terms but are unfamiliar with their usage, you may want to look at a simple example at the end of this solution before proceeding.

If we had 5 colonies, matrices for some of the changes would look as follows:

die 3 0

reproduce 2 5

copy 1 3

teleport 2 4

swap 0 2

merry-go-round 0 0

Assume that X₁, X₂, ..., X_M are the matrices corresponding to the changes given in the input file. Let X = X₁ * X₂ * ... * X_M be their product. As matrix multiplication is associative, the vector (1, 1, ..., 1) * X will contain the numbers of bacteria in the colonies after M seconds. Similarly, the vector (1, 1, ..., 1) * X^t * X₁ * X₂ * ... * X_r will contain the numbers of bacteria in the colonies after tM+r seconds.

So far we were silently ignoring the fact that we have to compute everything modulo K. We will keep on ignoring this fact. Just note that this doesn't affect the linearity of the operations (read: doesn't cause any problems).

We now have to compute the vector (1, 1, ..., 1) * X^t * X₁ * X₂ * ... * X_r effectively. Let t=floor(T/M), r=T mod M. We start by computing X. Note that we get the product X₁ * X₂ * ... * X_r as an intermediate result. We now just have to compute X^t. This can be done effectively using a simple recurrent formula: X^2t=(X^t)², X^2t+1=X * (X^t)². So if we want to compute X^t, we first compute X^floor(t/2) recursively and then we only need one or two matrix multiplications to compute the desired matrix X^t.

The time complexity of a simple simulating algorithm is O(NT). What about the second algorithm? The cost of multiplying two matrices is O(N³). We need M multiplications to compute X and then we need O(lg t)=O(lg (T/M)) multiplications to compute X^t. The total time complexity is also O(N³ * ( M + lg (T/M) ) ). For large values of T this solution is much faster.

Hint: As you maybe noticed, K in both input files is the same. Its last digits are: ...2890625. Yes, it is a power of 5, namely K = 5⁹⁶. If you noticed this you could internally represent all the big numbers in base 5 (instead of base 10) and then you could do all computations modulo K "for free".

For those of you unfamiliar with algebra a simple example. Let Fⁱ be the famous Fibonacci numbers. (F⁰=0, F¹=1, Fⁿ⁺²=Fⁿ⁺¹+Fⁿ). Let A be the following matrix:

Now suppose we start with the vector (0,1). After we multiply it by A n times, we get the vector (Fⁿ,Fⁿ⁺¹). Matrix multiplication is associative (but not commutative!), therefore multiplying a vector n times by the matrix A gives the same result as multiplying it once by the matrix A * A * ... * A = Aⁿ. The matrix Aⁿ may be computed using O(lg n) matrix multiplications. In this way we are able to compute the n-th Fibonacci number in time O(lg n).