PROBLEM LINK:Author: Bhuvnesh Jain Tester: Bhuvnesh Jain Editorialist: Bhuvnesh Jain DIFFICULTY:EASY PREREQUISITES:Matrix Exponentiation, Modular Multiplication PROBLEM:Calculate the number of times fibonacci(k) is called in the recursive function given for fibonacci sequence. EXPLANATION:The solution is basically $(nk+1)^{th}$ Fibonacci number for k>=1. The above can be proved by induction. Proof By Induction (we will prove here for $k \geq 1$) For n=0, there are no value of $k$ possible, so the proposition is trivially true. For n=1, we can only pick k=1. It is true that fibonacci(1) appears one time i.e. $F_{1−1+1} = F_{1} = 1$ Now we assume that our proposition is valid for all numbers smaller than n, (strong induction) and we’ll prove it for n. Let $1 \leq k \leq n$. Let us draw the recursion tree for $F_{n}$, which we call $T_{n}$. If $k = n$, then clearly $F_{n}$ only shows up 1 time in $T_{n}$ i.e at the root of the recusion tree, so the result holds. Likewise, if $k = (n−1)$, the only place we see $F_{n−1}$ is as the root of our left subtree, the larger one. So the result holds in that case as well, since $F_{n−(n−1)+1} = F_{2} = 1$. Let us then assume that $k \leq (n2)$, which allows us to use the inductive hypothesis on the left and right subtrees of $T_{n}$. By induction, the number of times $F_{k}$ appears in the left subtree is $F_{n−1−k+1} = F_{n−k}$, and the number of times it appears in the right subtree is $F_{n−2−k+1} = F_{n−k−1}$. Thus the number of times it appears in $T_{n}$ is the sum of values at both the subtrees, i.e. $F_{n−k} \ + \ F_{n−k−1} = F_{n−k+1}$, which was to be shown. Hence By Principle of mathematical induction the result holds all n and $k \geq 1$. But for k=0 the answer is $(n1)^{th}$ Fibonacci number. The corner case of k=0 can be seen from the recursion tree ${T}_{n}$ drawn showing that it occurs the same number of time as k=2. So the formula is (n2+1) = (n1) as stated above. To find the $n^{th}$ fibonacci number, we can use Modular exponentiation which gives a complexity of O(log n). But there is a more faster way to do this. You can refer to Codeforces blog for this. My solution uses the same concept but in a bit different and faster way. Also, the test cases were weak as most of the solutions should have failed. As per the constraints, the modulo should be taken m where 1<=m<=$10^{12}$. As ($10^{12}$. $10^{12}$) will overflow in C++, Java etc. without using big integer libraries, we needed to use Modular multiplication. One way to do this is using the same concept as modular multiplication and replacing the multipplication operations by additions. Below is the C++ function to do the same.
You can also use a O(1) hack for the above as given in Praveen Dhinwa's blog. COMPLEXITYO(${log}^2$n) or O(logn), depending on implementation of Modular multiplication function. AUTHOR'S SOLUTION:Author's solution can be found here. asked 26 Mar '16, 02:13

Proof please :) answered 26 Mar '16, 02:20
