 # codeforces 166E help needed (binary matrix exponentiation) for a begineer

Just learnt Binary Matrix Exponentiation for Codeforces 166E problem from:

Youtube: Gaurav Sen’s (gkcs) Matrix Exponentiation video

As there are a few blogs along with tutorial on codeforces itself for the problem, and some google results includes solutions as well. I have already read them but couldn’t understand the base cases and the matrix formation that we will be multiplying with itself to some power , then using DP and finally multiplying with base cases matrix to obtain actual solution.

Probably they weren’t beginners friendly or least I couldn’t understand any of them.

# I will be glad if someone help me out explaining his solution, or a brief description would be fine.

Codeforces 166E

Couldn’t think of any of the ways of solving 166E as defined in tutorial except recursive tree traversal solution which exceeded time limit obviously: My solution: 32205350

Will be glad to be guided if needs to learn something else.

@gkcs I’ll be glad if you help me 1 Like

# I found this in comment section and finally got it,

Let Ai denote number of ways to finish near the vertex A after i moves (same for Bi, Ci, Di). Easily,

Ai = Di - 1 + Bi - 1 + Ci - 1

Bi = Di - 1 + Ai - 1 + Ci - 1

Ci = Di - 1 + Ai - 1 + Bi - 1

Di = Ai - 1 + Bi - 1 + Ci - 1

with the initial conditions

A0 = 0, B0 = 0, C0 = 0, D0 = 1

Due to the symmetry A_i=B_i=C_i=ABC_i, so

ABCi = Di - 1 + ABCi - 1 + ABCi - 1 = Di - 1 + 2 * ABCi - 1

Di = ABCi - 1 + ABCi - 1 + ABCi - 1 = 3 * ABCi - 1

## and

TETRAHEDRON : can this problem be think in a way that if u want to reach at D in n steps,
then to travel n — 1 steps 3 ^ (n — 1) ways possible, now this case include that if u reached at D in n — 1 steps
therefore to reach in n steps ans(in n steps) = 3 ^ (n — 1) — ans(in n — 1 steps);
which is a DP solution eg — to reach in 1 steps = 0 to reach in 2 steps — 3 ^ (2 — 1) — 0;
to reach in 3 steps — 3 ^ (3 — 1) — 3 = 6 to reach in 4 steps — 3 ^ (4 — 1) — 6 = 21
to reach in 5 steps — 3 ^ (5 — 1) — 21 = 60

## and

Let f[A][j] is the number of ways from D to A by going j steps,as same,f[B][j], f[C][j] and f[D][j],
we know f[D] = 1, f[A, B, C] = 0(because the ant starts at D).

then you get four equations below:

f[A][j] = f[B][j - 1] + f[C][j - 1] + f[D][j - 1]

f[B][j] = f[A][j - 1] + f[C][j - 1] + f[D][j - 1]

f[D][j] = …

you can solve this problem in O(n),the answer is f[D][n] mod 1e9+7.

but it’s too slow.you can express the four equations by matrix.then it’s obvious to solve the problem by
matrix fast power algorithm in O(lg n).