Solving a relation
Practice
0 (0 votes)
Dynamic programming
Hard
Recurrence relation
Recurrence relations
Algorithms
Dp
Matrix exponentiation
Advanced
Problem
75% Success 16 Attempts 50 Points 5s Time Limit 256MB Memory 1024 KB Max Code
You are required to determine the \(n^{th}\) terms of the following relation:
\(f(0)=p\)
\(f(1)=q\)
\(f(2)= r\)
\(for n>2\)
\(f(n)= a*f(n-1) + b*f(n-2) + c*f(n-3) +g(n)\)
\(where\ g(n)=n*n*(n+1)\)
Since the \(n^{th}\) term can be too large, therefore you are required to print \(f(n)\ modulo\ (1000000007)\).
Input format
- First line: \(t\) denoting the number of test cases
- Each of the \(t\) line: Seven integers \(p,\ q,\ r,\ a,\ b,\ c,\ n\)
Output format
For each test case, print \(f(n) modulo(1000000007)\) that represents the \(n^{th}\) term of the sequence in a new line.
Constraints
\(1 \leq t \leq 50\)
\(1 \leq p,q,r,a,b,c,n \leq 10^{18}\)
Explanation
In Test case 4:
For the given values of p,q,r,a,b,c
f[0]= 1
f[1]= 2
f[2]= 3
f[3]= 1*f[2] + 1*f[1] + 1*f[0] + 3*3*(3+1)
f[3]= 1 + 2 + 3 + 36
f[3]= 42
Code Editor
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
Tags:
AlgorithmsOpenApprovedHard
Points:50
Tags:
Hard
Points:50
14 votes
Tags:
Dynamic ProgrammingHardAlgorithmsMathematicsOpenApproved
Editorial
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Results
Custom Input
Run your code to see the output