**_This Problem was given by [user:DeadlyCritic,2020-06-24]_ as a challenge**↵
↵
###### Statement:↵
Given [problem:1369D] solve it for $10^{18}$ without using Matrix Exponentiation.↵
↵
###### Solution:↵
↵
In order to maximize the number of Claws, the basic idea is to keep track of $no. of nodes$ with no child at any $k^{th}$ $level$.↵
So, max no of nodes that can be painted yellow for any $nth$ level is given by:↵
↵
\begin{equation}\operatorname{sum}=4 *\left(\sum_{i=0}^{\left(\frac{n-2}{3}\right)} a_{((n-2) \% 3+3 i)}\right)\end{equation}↵
↵
where, $a_{i}=$ no of nodes with no child at $i^{th}$ level↵
↵
Now in order to get $a_{i}$ we use this recurrence:↵
\begin{equation}f(x)=2 * f(x-2)+f(x-1)\end{equation}↵
↵
Linear recurrence like this can be solve using characteristic equation, i will not get into details for the sake of keeping this blog short!↵
Here is the equation:↵
↵
\begin{equation}\begin{array}{c}↵
f(x)-2 * f(x-2)-f(x-1)=0 \\\\↵
r^{n}-2 * r^{n-2}-r^{n-1}=0 \\\\↵
r^{n-2}\left(r^{2}-2-r\right)=0↵
\end{array}\end{equation}↵
↵
From above, quadratic equation has two distinct solutions $r1 = 2$, $r2 = -1$↵
↵
Now, \begin{equation}a_{n}=\alpha r_{1}^{n}+\beta r_{2}^{n}\end{equation} is the general term of the series we build from recurrence and, \begin{equation}\alpha=\frac{1}{3} \text { and } \beta=-\frac{1}{3}\end{equation} that can be easily found using initial conditions i.e. $a_{0} = 0$ & $a_{1} = 1$↵
↵
Till now, \begin{equation}a_{n}=\frac{1}{3} *(2)^{n}-\frac{1}{3} *(-1)^{n}\end{equation}↵
Finally, we have deduced the summation into a nice formula using geometric series↵
\begin{equation}\operatorname{sum}=4 * \frac{1}{3} *\left(2^{(x \% 3)} *\left(\frac{8^{\left(\left|\frac{x}{3}\right|+1\right)}-1}{7}\right)-(-1)^{(x \% 3)} *\left(\frac{1-(-1)^{\left(\left|\frac{x}{3}\right|+1\right)}}{2}\right)\right)\end{equation}↵
↵
where $x = n - 2$↵
↵
Although, there can be many questions related to each step, but i'll leave that upon reader to think, all i wanted to is give the basic idea on how to solve this type of recurrence. Feel free to correct any errors.↵
It was nice experience to write my first blog :)↵
↵
My Submission : [submission:84891174]
↵
###### Statement:↵
Given [problem:1369D] solve it for $10^{18}$ without using Matrix Exponentiation.↵
↵
###### Solution:↵
↵
In order to maximize the number of Claws, the basic idea is to keep track of $no. of nodes$ with no child at any $k^{th}$ $level$.↵
So, max no of nodes that can be painted yellow for any $nth$ level is given by:↵
↵
\begin{equation}\operatorname{sum}=4 *\left(\sum_{i=0}^{\left(\frac{n-2}{3}\right)} a_{((n-2) \% 3+3 i)}\right)\end{equation}↵
↵
where, $a_{i}=$ no of nodes with no child at $i^{th}$ level↵
↵
Now in order to get $a_{i}$ we use this recurrence:↵
\begin{equation}f(x)=2 * f(x-2)+f(x-1)\end{equation}↵
↵
Linear recurrence like this can be solve using characteristic equation, i will not get into details for the sake of keeping this blog short!↵
Here is the equation:↵
↵
\begin{equation}\begin{array}{c}↵
f(x)-2 * f(x-2)-f(x-1)=0 \\\\↵
r^{n}-2 * r^{n-2}-r^{n-1}=0 \\\\↵
r^{n-2}\left(r^{2}-2-r\right)=0↵
\end{array}\end{equation}↵
↵
From above, quadratic equation has two distinct solutions $r1 = 2$, $r2 = -1$↵
↵
Now, \begin{equation}a_{n}=\alpha r_{1}^{n}+\beta r_{2}^{n}\end{equation} is the general term of the series we build from recurrence and, \begin{equation}\alpha=\frac{1}{3} \text { and } \beta=-\frac{1}{3}\end{equation} that can be easily found using initial conditions i.e. $a_{0} = 0$ & $a_{1} = 1$↵
↵
Till now, \begin{equation}a_{n}=\frac{1}{3} *(2)^{n}-\frac{1}{3} *(-1)^{n}\end{equation}↵
Finally, we have deduced the summation into a nice formula using geometric series↵
\begin{equation}\operatorname{sum}=4 * \frac{1}{3} *\left(2^{(x \% 3)} *\left(\frac{8^{\left(\left|\frac{x}{3}\right|+1\right)}-1}{7}\right)-(-1)^{(x \% 3)} *\left(\frac{1-(-1)^{\left(\left|\frac{x}{3}\right|+1\right)}}{2}\right)\right)\end{equation}↵
↵
where $x = n - 2$↵
↵
Although, there can be many questions related to each step, but i'll leave that upon reader to think, all i wanted to is give the basic idea on how to solve this type of recurrence. Feel free to correct any errors.↵
It was nice experience to write my first blog :)↵
↵
My Submission : [submission:84891174]
