Latest Updates ☛
- Graphs: Introduction of graphs and types of graphs
- SPOJ : Geeky solves geeky solution
- Solution Code : Pass the time problem on SPOJ.
- Find the minimum shortest path solution in c language ! !
- Code
Author
Welcome !
Heya ! Firstly thanks for giving look to this website .Here you can find all the stuff related to programming plus its solutions means a pack for learners and coders.
So keep visiting and enjoy learning and browsing this Code Author ! !
About Me
- Java Programs
- C++
C++ Programs List
- Books
- C & Data Structures
Data Structures
Reference Book
This is a basic book for a starter to learn data structures in c programming language.Filled with total explanation of all programs working and many more.Read more...
- Privacy Policy
- Others
Saturday, September 7, 2013
Butter like to solve recurrences SPOJ' problem- Solution O(log n)
Question :
Butters likes to solve Recurrence Relations. He wants to solve them really fast. He got this relation:
F(n) = 2*F(n-1) + 3*F(n-2) with F(1)=1 and F(2) =2
So the series becomes:
1 2 7 20 61 ...
So the first term is 1, 2nd term is 2, 3rd term in 7 and so on. He wants to know the Nth term of this series. Since the answer can be really large, he wants to find it moudlo 1000000007.
Butters likes to solve Recurrence Relations. He wants to solve them really fast. He got this relation:
F(n) = 2*F(n-1) + 3*F(n-2) with F(1)=1 and F(2) =2
So the series becomes:
1 2 7 20 61 ...
So the first term is 1, 2nd term is 2, 3rd term in 7 and so on. He wants to know the Nth term of this series. Since the answer can be really large, he wants to find it moudlo 1000000007.
Inputs
First line will contain "T" the no. of test cases. Each of the next "T" lines will contain an integer N, the term which Butters wants to find out.
Outputs :
For each test case print the Nth term of this series modulo 1000000007.
For each test case print the Nth term of this series modulo 1000000007.
Constraints
1 <= T <= 10^5 , 1 <= N <= 10^9
1 <= T <= 10^5 , 1 <= N <= 10^9
Level : Thinker,Admirer
Solution to the Problem :
//this is an O(log n) solution for finding the nth fibonacci number
#include<stdio.h>
long long int mod =1000000007;
void multiply(long long int m[][2],long long int n[][2])
{
long long int c00=((m[0][0]*n[0][0])%mod+(m[0][1]*n[1][0])%mod)%mod;
long long int c01=((m[0][0]*n[0][1])%mod+(m[0][1]*n[1][1])%mod)%mod;
long long int c02=((m[1][0]*n[0][0])%mod+(m[1][1]*n[1][0])%mod)%mod;
long long int c03=((m[1][0]*n[0][1])%mod+(m[1][1]*n[1][1])%mod)%mod;
m[0][0]=c00;
m[0][1]=c01;
m[1][0]=c02;
m[1][1]=c03;
}
void power(long long int m[][2],long long int n)
{
if(n==1)
return;
if(n==2)
{
multiply(m,m);
return;
}
long long int temp[2][2];
temp[0][0]=m[0][0]%mod;
temp[0][1]=m[0][1]%mod;
temp[1][0]=m[1][0]%mod;
temp[1][1]=m[1][1]%mod;
power(m,n/2);
multiply(m,m);
if(n%2!=0)
multiply(m,temp);
}
void fibonacci(long long int n)
{
long long int m[2][2];
m[0][0]=2;
m[0][1]=1;
m[1][0]=3;
m[1][1]=0;
power(m,n-2);
long long int x[2][2]={7,2,2,1};
multiply(x,m);
printf("%lld\n",x[1][0]%mod);
}
main()
{
long long int t;
scanf("%lld",&t);
while(t--)
{
long long int k;
scanf("%lld",&k);
if(k==1)
printf("1\n");
else if(k==2)
printf("2\n");
else
fibonacci(k);
}
}
}
