Sauron Eye | Solve programming problems on HackerEarth

Sauron Eye | Solve programming problems on HackerEarth
Gandalf the Grey is in trouble as Saurons eye Rearrived in the middle world. Now he has to prepare for the war, But in order to defeat Sauron he has to know the power of saurons eye on the day in which he wants to attack.
According to the Elves(Good Friends of Gandalf),Gandalf came to know that saurons eye power on current day is equal to 3 time to its power on previous day minus the power on a day before previous day.
Now Gandalf ask Frodo to give him the power of the Saurons Eye on nth day, but poor Frodo is not good in mathematics so he ask for help from you.
Given the nth day you have to give Frodo power of Saurons eye on that day mod 10⁹ + 7.
Note You can assume the power of sauron eye is 1 on 1st day
and 3 on 2nd day.

As you have rightly identified given n solution is
f(n)= 3*f(n-1)-f(n-2);
This can be solved using matrix exponentiation as recurrance matrix
[3 -1 ]
[1 0 ]
you can read about matrix exponentiation here
http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html
https://www.hackerearth.com/submission/1950666/

1. static int mod = (int)(1E9 + 7);
2. static long fib(long n)
3. {
4. long F[][] = {{3,-1},{1,0}};
5. if (n == 0)
6. return 0;
7. else if(n==1)
8. return 1;
9. power(F, n-1);
10. return F[0][0];
11. }
13. /* Optimized version of power() in method 4 */
14. static void power(long F[][], long n)
15. {
16. if( n == 0 || n == 1)
17. return;
18. long M[][] = {{3,-1},{1,0}};
20. power(F, n/2);
21. multiply(F, F);
23. if (n%2 != 0)
24. multiply(F, M);
25. }
27. static void multiply(long F[][], long M[][])
28. {
29. long x = ((F[0][0]*M[0][0])%mod + (F[0][1]*M[1][0])%mod)%mod;
30. long y = ((F[0][0]*M[0][1])%mod + (F[0][1]*M[1][1])%mod)%mod;
31. long z = ((F[1][0]*M[0][0])%mod + (F[1][1]*M[1][0])%mod)%mod;
32. long w = ((F[1][0]*M[0][1])%mod + (F[1][1]*M[1][1])%mod)%mod;
34. F[0][0] = x;
35. F[0][1] = y;
36. F[1][0] = z;
37. F[1][1] = w;
38. }

Read full article from Sauron Eye | Solve programming problems on HackerEarth