Strange Fibonacci:
Its Advaita time, Subash and Rohit are playing a game where Rohit gives Subash a strange fibonacci sequence where F(n) = 5*F(n-2) + 4*F(n-1). Here F(n) denotes the nth term of the sequence.Rohit asks Subash to find out the nth term of the given sequence under modulo 109+7.Help Subash to find the answer.
Input
• The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains 3 integers FO, F1 and N. where FO is the Oth term of the sequence F1 is 1st term of the sequence and N denotes the Nth
term whose value you need to find out.
Output
• For each test case, output a single number containing the value of F(n) under modulo 109+7 i.e the Nth term of the given sequence.
Constraints
• 1 ≤ T≤ 100000
• O≤ FO≤ 1000000
• 0≤ F1 ≤ 1000000
0 ≤ N ≤ 1000000
Sample input
1
0 1 2
Sample output
4
Program:
#include <stdio.h>
#define mod 1000000007
long int f0,f1;
long int recur(long int n){
if(n==0)
return f0;
else if(n==1)
return f1;
else
return(5*recur(n-2)+4*recur(n-1));
}
void func(){
long int n;
scanf("%ld%ld%ld",&f0,&f1,&n);
long int ans=recur(n);
printf("%ld\n",ans%mod);
}
int main(){
long int T;
scanf("%ld",&T);
while(T--)
func();
}
Explanation:
Program that reads in a number of test cases (T) and for each test case, it reads in three integers f0, f1, and n, and calculates the nth term of the following recursive sequence:
f(n) = 5 * f(n-2) + 4 * f(n-1)
where f(0) = f0 and f(1) = f1. The program then outputs the answer modulo 1000000007.
Here's how the program works:
1.The first line of the program includes the standard input/output library (stdio.h).
2.The second line defines a constant value mod as 1000000007.
3.The next two lines declare two long integers f0 and f1, which are used to store the first two terms of the sequence.
4.The next line declares a recursive function called recur that takes a single argument n, which is the term of the sequence to be calculated.
5.The recur function checks the value of n. If n is equal to 0, the function returns f0. If n is equal to 1, the function returns f1. Otherwise, the function calculates f(n) using the recursive formula and returns the result.
6.The next line declares a void function called func that reads in the values of f0, f1, and n from the user and then calculates the nth term of the sequence using the recur function. The result is stored in the variable ans.
7.The final line of the func function outputs the result modulo mod.
8.The main function reads in the number of test cases (T) and then calls the func function T times, once for each test case.
Overall, this program implements a recursive algorithm to calculate the nth term of a given sequence and outputs the result modulo a specified value.
0 Comments