Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Matrix
Difference between en76 and en77, changed 559 character(s)
Yeah, yeah, I know you expect from me matrix jokes. What if I told you I have no jokes on that ? So, just take the blue pill and go into serious stuff like ... ↵

### Cutting to the chase ↵

I personally find matrix multiplication as the guy who sells stolen phones at the corner of the street. I mean, you get stuff at lower price but it can break in two days and you can get busted by the cops. Or not. I really need to find better metaphors... ↵

Matrix multiplication is a well known method. People wrote on it before quite good articles, but I think you might get stuff simpler just by looking over some problems. For the ones who are familiar with the topic, you can skip to the last two problems.↵

### Getting high fast↵

Now I need to find better subtitles... However, first of all to know logarithmic matrix multiplication, you have to know logarithmic multiplication.↵

Basically we have to compute $x^n$ considering the multiplication operation take $O(1)$ time. Take it straight forward we get $x^n = x * x * .. * x$ , so $O(N)$. Let's try to reduce it step by step. Let's take $x^n = x^2 * x^2 * ...$. And we multiply by $x$ if n is odd. This should work fine and the constant is reduced at half. Right... Similarly we can go to $x^n = x^{sqrt(n)} * x^{sqrt(n)} * ...$ and this goes to $O(sqrt N)$. This reasoning stops here.↵

To get it faster you have to simply observe that $x^n = x^{n/2} * x^{n/2}$ for n even and $x^n = x^{n/2} * x^{n/2} * x$ for n odd. The two terms are the same and the third is constant, so we really need to compute $x^{n/2}$ once. And $x^{n/4}$ once. And so on. Therefore the $O(log N)$ complexity. ↵

Now, notice that we did not specified that x is an integer or a number. The same rules hold for other mathematical associative structures such as matrices. ↵

### Don't get stuck with struct↵

If you sayin' Y U NO REMEMBER MATRIX, then let me refresh your maths knowledge. You don't really need to know much about matrices to use put recurrences in a matrix multiplication form. Multiplying squared matrices is straight forward. Given two matrices their product is ↵

$M * N = \begin{bmatrix} a_1 & a_2 \\ - & - \\ a_3 & a_4 \end{bmatrix} * \begin{bmatrix} b_1 & | & b_2 \\ b_3 & | & b_4 \end{bmatrix} = \begin{bmatrix} {a_1 * b_1 + a_2 * b_3} & {a_1 * b_2 + a_2 * b_4} \\ {a_3 * b_1 + a_4 * b_3} & {a_3 * b_2 + a_4 * b_4} \end{bmatrix}$↵

Each element in each row in $M$ is multiplied by its correspondent in the columns of $N$. If you find it simpler to remember, just imagine horizontal rows splitting matrix $M$ and vertical row splitting matrix $N$ and then match each row with each column. ↵

Let's make a structure in which we keep a matrix. If new to matrices you should get an idea how matrix multiplication works from the code below.↵

~~~~↵
struct matrix {↵
// N is the size of the matrix↵
int m[N][N];↵
matrix()↵
{↵
memset(m,0,sizeof(m));↵
}↵
matrix operator * (matrix b)↵
{↵
matrix c = matrix();↵
for (int i = 0; i < N; ++i)↵
for (int j = 0; j < N; ++j)↵
for (int k = 0; k < N; ++k) ↵
c.m[i][j] = (c.m[i][j] + 1LL * m[i][k] * b.m[k][j]) % M;↵
return c;↵
}↵
...↵
};↵
~~~~↵

Notice that we define the multiplication operation. We specifically did this so we can use a matrix exactly as a number in the logarithmic multiplication algorithm. So the code will be the same for an int and a matrix. Pretty cool if I do say so. And I do.↵

~~~~↵
matrix modPow(matrix m,int n)↵
{↵
if ( n == 0 )↵
return unit; // the unit matrix - that is 1 for principal diagonal , otherwise 0↵
matrix half = modPow(m,n/2);↵
matrix out = half * half;↵
if ( n % 2 )↵
out = out * x;↵
return out; ↵
}↵
~~~~↵

Note that we could have defined an operator for power multiplication or used a template that we could have applied for a general type, but I find the implementation above more clear due to the clarity of the recurrence.↵

### $N$-th Fibonacci term↵

For starters, let's define:↵

$F_n = F_n-1 + F_n-2$ with $F_1 = 1, F_2 = 1$↵

We need to put this in the form of a matrix recurrence. Well, each term is dependent of other consecutive two. This is a good clue we need just a 2 row matrix. So, from $F_{n-2}$ and $F_{n-1}$ we need to compute $F_n$. To keep the recurrences squared we will compute from the pair $(F_{n-2},F_{n-1})$ the pair $(F_{n-1},F_n)$. ↵

$F_n = F_{n-1} * 1 + F_{n-2} * 1$↵
$F_{n-1} = F_{n-1} * 1 + F_{n-2} * 0$↵

Or, as matrices:↵

$\begin{bmatrix} F_{n-2} & F_{n-1} \\ 0 & 0 \end{bmatrix} * \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} F_{n-1} & F_n \\ 0 & 0 \end{bmatrix}$↵

Going one step backwards we got:↵

$\begin{bmatrix} F_{n-3} & F_{n-2} \\ 0 & 0 \end{bmatrix} * \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} ^ 2 = \begin{bmatrix} F_{n-1} & F_n \\ 0 & 0 \end{bmatrix}$↵

Finally:↵

$\begin{bmatrix} F_{1} & F_{2} \\ 0 & 0 \end{bmatrix} * \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} ^ {n-2} = \begin{bmatrix} F_{n-1} & F_n \\ 0 & 0 \end{bmatrix}$↵

Getting $\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$ at power n takes logarithmic time , so that is just... fast.↵

### Bits and pieces↵

As you can see, this technique can be used to calculate the n-th term of a linear recurrence. In the following [example](http://infoarena.ro/problema/nkbiti) we need to find out how many arrays of length n with maximum k consecutive 0 bits are there. ( $n \le 10^9 , k \le 40$  )↵

Let's suppose n is small enough so we can use dynamic programming to solve the problem. Denote $D_{n,k}$ = number of arrays of length n which end in k number of 0s↵

As you can guess one can make two moves: add a 0 and add a 1. Therefore, from state $(n,k)$ we can go to states $(n+1,k+1)$ and $(n+1,0)$. So $D_{n,0} = \sum_{i = 0}^k D_{n-1,i}$ and $D_{n,k} = D_{n-1,k}$. As we did before, let's write down all recurrences we are interested in. ↵

$D_{n,0} = \sum_{i = 0}^k D_{n-1,i}$↵

$D_{n,1} = D_{n-1,0}$↵

$D_{n,2} = D_{n-1,1}$↵

$...$↵
↵
$D_{n,k} = D_{n-1,k}$↵

The matrix recurrence will come straight away:↵

$\begin{bmatrix} D_{n-1,0} & D_{n-1,1} & ... & D_{n-1,k} \\ 0 & 0 & ... & 0 \\ ...&...&&... \\ 0 & 0 & ... & 0 \end{bmatrix} * \begin{bmatrix} 1 & 1 & ... & 0 \\ 1 & 0 & ... & 0 \\ ...&...&&... \\ 1 & 0 & ... & 1 \end{bmatrix} = \begin{bmatrix} D_{n,0} & D_{n,1} & ... & D_{n,k} \\ 0 & 0 & ... & 0 \\ ...&...&&... \\ 0 & 0 & ... & 0 \end{bmatrix}$↵

As you can see, now the complexity of the solution is reduces from $O(N*K)$ to $O(log N*K^3)$, the $K^3$ being the complexity of multiplying 2 K-size matrices.↵

### How big can it get ? ↵

Now seriously, I really need better subtitles. Problem (Chimney)[http://community.topcoder.com/stat?c=problem_statement&pm=11512&rd=14546] from TopCoder can be solved similarly with the problems above.↵

Usually, when we got a big $N$, this is a hint in favor of logarithmic multiplication. So we have to find a recurrence. More specifically, we have to find a good way to represent a state.↵

You can also note that we are not really interested how many layers have been completed, but what are the last moves made. So we can have the next forms of completed blocks in the last layers:↵
↵
~~~~↵
+-----+--+  +-----+--+  +-----+--+  +-----+--+
+-----+--+  +-----+--+  +-----+--+  +-----+--+
|xxxxx|  |  |     |  |  |xxxxx|  |  |     |xx|

+--+--
|  |   |  |  +--+--|  |  +--+--|  |   +--+--|xx|    ↵
|  |  |  |  |xx|  |  |   |xx|↵
|  |  |  |  |xx|  |xx|    ↵
|
+--+--|+  |  xx+--+--|+  |  +--+--|+  |  xx+--+--|xx|  +  ↵
|  |     |  |xx|xxxxx|  |  |xxxxx|  |xx|xxxxx|  ↵
+--+--|  |---+  +--+--|xx|---+  +--+--|xx|---+  +--+--|##|---+
|  |  |1  |  |xx|  |  |  |  |2  |  |  |xx|  |xx|  |xx         3           4↵

+-----+--+  +-----+--+  +-----+--+  +-----+--+↵
|     |
|  |   |  |xx|  |##|     |xx|  |##|     |xx|  |##|  ↵
|

+--+--+|  |xx  +--+--+  |xx|  +--+--+  |xx+--+--+  |xx|xx|  +--+--|oo| ↵
+--+--+|  |xx  +--+##+  |xx+--+##+  |xx+--+##+  ↵
--|xx|  +--+--|xx|  +--+--|oo|↵
|xx
|  |     |  |xx|xxx  |oo|  |xx|  |oo|  |xxxxx|  |xx|xxxxx|  oo|↵
|xx+--+--+  |xx+--+oo+  |xx+--+oo+  |xx+--+oo+↵
|=====xxx|  |xx|xxx##oo|  |===== ##oo|  |===@@@@@|
+--+-----+  +--+-----+  +--+-----+  +--+-----+
+--+-----+  +--+-----+  +--+-----+  +--+-----+
5            6           7           8↵
↵
~~~~↵

xx represent brick on the n-th layer. == and 
##&& are bricks on the n+1-th layer. @@ are bricks on the n+2-th layer.↵
The special thing is we do not care what is the orientation of the chimney as all its bricks are similar, so for one brick on n-th layer ( pic 1 ) we treat all 4 possible displays the same. Another important thing to notice is that after we place two bricks one next to the other we can complete another brick in the layer above. ( pics 5,6 and 7 ). Finally, we can just add another brick to the n+2-th layer. ( pic 8 ) For simplicity, we should also consider the free layer ( a layer that contains no bricks ).↵

Therefore, this problem can be solved by matrix multiplication, building a 9 per 9 matrix and logarithmic multiplying it. You can see my implementation [here](http://ideone.com/T6HXhE).↵

### Summing up↵

What we looked at today can be a good tool, no doubt. But as a personal advice, use it only when is necessary outside contests. Some problems are intended to be solved in a different way and people can skip useful stuff by overusing the method described above.↵

I also recommend this [blog post](http://fusharblog.com/solving-linear-recurrence-for-programming-contest/), which is really good.↵

### PS↵

Thank you for reading and please state your opinion on my tutorial. ( or, more specifically, on my writing style and how useful you find the material presented ) Any suggestions for next tutorial are welcome.↵

You can find my previous article [here](http://codeforces.com/blog/entry/20489).↵

Hope you enjoyed!

#### History

Revisions Rev. Lang. By When Δ Comment
en83 DanAlex 2016-03-08 03:35:36 59 Tiny change: ' & ... & 0\\ 0 && 0 & ... ' -
en82 DanAlex 2016-03-08 03:24:58 2 Tiny change: '= D_{n-1,k} $\n\nThe' -> '= D_{n-1,k-1}$\n\nThe'
en81 DanAlex 2016-02-07 15:39:28 6 Tiny change: ' problems.\n\n### Ge' -> ' problems. [cut]\n\n### Ge'
en80 DanAlex 2016-01-25 16:52:59 2 Tiny change: 't = out * x;\n retur' -> 't = out * m;\n retur'
en79 DanAlex 2015-10-27 01:46:23 8
en78 DanAlex 2015-10-27 01:45:38 4 Tiny change: '== and && are bric' -> '== and oo are bric'
en77 DanAlex 2015-10-27 01:45:03 559
en76 DanAlex 2015-10-25 16:59:30 0 (published)
en75 DanAlex 2015-10-25 16:54:33 748
en74 DanAlex 2015-10-25 16:45:17 427
en73 DanAlex 2015-10-25 16:41:18 31
en72 DanAlex 2015-10-25 16:40:30 1120
en71 DanAlex 2015-10-25 16:22:13 1 Tiny change: '-+ \n~~~~~' -> '-+ \n~~~~'
en70 DanAlex 2015-10-25 16:21:53 797
en69 DanAlex 2015-10-25 16:08:48 706
en68 DanAlex 2015-10-25 15:57:10 66
en67 DanAlex 2015-10-25 15:55:47 97
en66 DanAlex 2015-10-25 15:54:38 8
en65 DanAlex 2015-10-25 15:53:27 18
en64 DanAlex 2015-10-25 15:52:45 7
en63 DanAlex 2015-10-25 15:52:11 2 Tiny change: '. & 0 \\ ... \\ 0 & 0' -> '. & 0 \\ .&.&. \\ 0 & 0'
en62 DanAlex 2015-10-25 15:51:21 376
en61 DanAlex 2015-10-25 15:46:52 32
en60 DanAlex 2015-10-25 15:45:55 20
en59 DanAlex 2015-10-25 15:45:10 191
en58 DanAlex 2015-10-25 15:43:23 12 Tiny change: 'here. ( $n<=10^9 , k <= 40$ )\n\' -> 'here. ( $n \le 10^9 , k \le 40$ )\n\'
en57 DanAlex 2015-10-25 15:42:56 36
en56 DanAlex 2015-10-25 15:42:01 76
en55 DanAlex 2015-10-25 15:39:58 6 Tiny change: 'm. Denote `D_{(n,k)}' = number ' -> 'm. Denote $D_{n,k}$ = number '
en54 DanAlex 2015-10-25 15:39:35 15
en53 DanAlex 2015-10-25 15:38:28 143
en52 DanAlex 2015-10-25 15:35:40 5
en51 DanAlex 2015-10-25 15:35:21 452
en50 DanAlex 2015-10-25 03:19:21 119
en49 DanAlex 2015-10-25 03:18:05 4 Tiny change: 'matrix} ^ (n-2) = \begin{' -> 'matrix} ^ {n-2} = \begin{'
en48 DanAlex 2015-10-25 03:17:48 182
en47 DanAlex 2015-10-25 03:16:40 206
en46 DanAlex 2015-10-25 03:14:12 7 Tiny change: 'matrix} 0 1 & 1 1 \end{bm' -> 'matrix} 0 & 1 \\ 1 & 1 \end{bm'
en45 DanAlex 2015-10-25 03:13:45 258
en44 DanAlex 2015-10-25 03:10:44 10
en43 DanAlex 2015-10-25 03:10:10 347
en42 DanAlex 2015-10-25 03:06:27 156
en41 DanAlex 2015-10-25 03:01:27 37 Tiny change: 'more clear.' -> 'more clear due to the clarity of the recurrence.'
en40 DanAlex 2015-10-25 03:00:37 186
en39 DanAlex 2015-10-25 02:58:28 7 Tiny change: ' c;\n }\n};\n~~~~' -> ' c;\n }\n ...\n};\n~~~~'
en38 DanAlex 2015-10-25 02:58:09 571
en37 DanAlex 2015-10-25 02:53:18 584
en36 DanAlex 2015-10-25 02:45:49 44
en35 DanAlex 2015-10-25 02:44:10 23
en34 DanAlex 2015-10-25 02:42:28 257
en33 DanAlex 2015-10-25 02:36:49 8 Tiny change: 'ix} b_1 & b_2 \\ b_3 & b_4 \en' -> 'ix} b_1 & | & b_2 \\ b_3 & | & b_4 \en'
en32 DanAlex 2015-10-25 02:36:17 5 Tiny change: '& a_2 \\ ---- \\ a_3 &' -> '& a_2 \\ - & - \\ a_3 &'
en31 DanAlex 2015-10-25 02:35:58 3 Tiny change: '& a_2 \\ - - \\ a_3 &' -> '& a_2 \\ ---- \\ a_3 &'
en30 DanAlex 2015-10-25 02:35:41 4 Tiny change: '& a_2 \\ ----- \\ a_3 &' -> '& a_2 \\ - - \\ a_3 &'
en29 DanAlex 2015-10-25 02:35:24 9 Tiny change: ' & a_2 \\ a_3 & ' -> ' & a_2 \\ ----- \\ a_3 & '
en28 DanAlex 2015-10-25 02:34:35 7 Tiny change: '{bmatrix} $= \n$\begin{bma' -> '{bmatrix} = \begin{bma'
en27 DanAlex 2015-10-25 02:34:14 4
en26 DanAlex 2015-10-25 02:33:38 18
en25 DanAlex 2015-10-25 02:32:46 5 Tiny change: '{bmatrix} = \n\begin{b' -> '{bmatrix} $=$\n\begin{b'
en24 DanAlex 2015-10-25 02:32:15 76
en23 DanAlex 2015-10-25 02:31:14 68
en22 DanAlex 2015-10-25 02:30:11 217
en21 DanAlex 2015-10-25 02:27:25 43
en20 DanAlex 2015-10-25 02:26:39 4
en19 DanAlex 2015-10-25 02:25:45 11
en18 DanAlex 2015-10-25 02:24:46 7
en17 DanAlex 2015-10-25 02:24:31 3
en16 DanAlex 2015-10-25 02:24:09 4
en15 DanAlex 2015-10-25 02:23:44 20
en14 DanAlex 2015-10-25 02:22:34 75
en13 DanAlex 2015-10-25 02:20:26 7
en12 DanAlex 2015-10-25 02:20:08 45
en11 DanAlex 2015-10-25 02:19:17 54
en10 DanAlex 2015-10-25 02:17:40 73
en9 DanAlex 2015-10-25 02:15:46 1 Tiny change: ' \n\n$M = \[a & b & c' -> ' \n\n$M = [a & b & c'
en8 DanAlex 2015-10-25 02:15:30 56
en7 DanAlex 2015-10-25 02:14:55 95
en6 DanAlex 2015-10-25 02:11:32 478
en5 DanAlex 2015-10-25 02:02:29 333
en4 DanAlex 2015-10-25 01:57:53 6 Tiny change: ' = x^{sqrt n} * x^{sqrt n} * ...$a' -> ' = x^{sqrt(n)} * x^{sqrt(n)} * ...$ a'
en3 DanAlex 2015-10-25 01:57:35 10
en2 DanAlex 2015-10-25 01:56:21 268
en1 DanAlex 2015-10-25 01:53:13 1004 Initial revision (saved to drafts)