Question: This is a question I had as an exercise. 

There are two types of bacteria. Say x and y. Every second they multiply while changing their type.

Type x becomes 2 y type and 1 x type (`x -> 2y + x`). Type y becomes 3 x type and 1 y type (`y -> 3x + y`). Other than that, 1 x type and 3 y type are born spontaneously (each second -> `x + 3y`).

The task is to calculate the number of bacteria after a given time `t`.

I wrote a code here:

```
x = 1
y = 1
t = 2

def calcFinalBacteria (x, y, t):
    for i in xrange (t):
        tempX = x + y * 3 # contribution by x bacteria (1) and y bacteria (3)
        tempY = x * 2 + y # contribution by x bacteria (2) and y bacteria (1)

        x += tempX + 1 - x # spontaneous addition of 1 x bacteria
        y += tempY + 3 - y # spontaneous addition of 3 y bacteria
    print x, y

calcFinalBacteria (x, y)

```

The time complexity of my code is O(t) here. But is there any way for improvement? For small inputs it is okay. But when I push t up to 10^18 and increase x, y up to 1000, it takes much time to find out

Answer: 
So if I'm understanding this right, `x' = x+3y+1` and `y' = 2x+y+3`. Suppose your initial population is ten x and seven y, and you want to evolve it by one step. This can be modeled with the following matrix multiplication:

```
|1 3 1|   |10|
|3 1 3| x | 7|
|0 0 1|   | 1|

```

So to find the answer, you need to repeat the matrix multiplication `t` times.

Although, the way you've written the code, each x turns into 2y and 0 x, not 2y and one x.
One small improvement.

You were adding the value to itself and the subtracting it's original value.

```
x = 1
y = 1
t = 2

def calcFinalBacteria (x, y, t):
    for i in xrange (t):
        tempX = x + y * 3 # contribution by x bacteria (1) and y bacteria (3)
        tempY = x * 2 + y # contribution by x bacteria (2) and y bacteria (1)

        x = tempX + 1 # spontaneous addition of 1 x bacteria
        y = tempY + 3 # spontaneous addition of 3 y bacteria
    print x, y

calcFinalBacteria (x, y)

```