Let us present infected people in one day as an object which has a defined operator ~*~. We want the operator to determine the infected people for the next day, based on two of the past days. Let us denote the first day with ~B~. We denote the second and every ~j^\text{th}~ day as ~K(j)~. Then we have:

$$\displaystyle \begin{align*} K(1) &= B \\ K(2) &= B*K(1) = B*B \end{align*}$$

We can think of a day as an array of ~0~s and ~1~s such that there is ~1~ in the ~i^\text{th}~ position if the ~i^\text{th}~ person was infected that day. The operator can then be implemented with a complexity of ~\mathcal O(M^2)~.

Let us take a look at the solution for day 3:

$$\displaystyle K(3) = B*K(2) = B*B*K(1) = B*B*B = B^3$$

Here we add an operator of exponentiation as a shortened writing of consecutive multiplication. Let us take a look at the properties of this operator.

$$\displaystyle B^i = B^{i-1}*B$$

This is obviously right because we have defined exponentiation as shorthand for consecutive multiplication.

$$\displaystyle B^i*B^i = B^{2i}$$

This relation is also true for our operator ~*~. It is now possible, using logarithmic exponentiation, to implement the operation with a complexity of ~\mathcal O(M^2 \log K)~ where ~K~ is a day we are interested in.

The algorithm:

power(B, k) =
  if k is 0,
    return {0, 1, 0, 0, ...}
  if k is even,
    half = power(B, k / 2)
    return half * half
  if k is odd,
    return power(B, k - 1) * B

If ~k~ becomes ~0~, we must return the object which will be the neutral element for the operator ~*~. In our case it is ~\{0, 1, 0, 0, \dots\}~.