Sequential Terms - Zauba Hiring Challenge

Link - https://www.hackerearth.com/challenges/hiring/zauba-campus-hiring-challenge19/

Sequential Terms

You are required to determine the n_{th} term of the provided sequence whose relation is as follows :
f(0) = p
f(1) = q
f(2) = r

for n > 2
f(n) = a \times f(n - 1) + b \times f(n-2) + c \times f(n - 3) + g(n)

where g(n) = n \times n \times (n + 1)

Note Since n_{th} term would be too large, therefore print the value as f(n) (mod (10^9 + 7))

Input Format

  • First line : t denoting the number of test cases
  • Each of the t lines : Seven integers p,q,r,a,b,c,n

Output Format
For each test case print f(n) \% (10^9 + 7) 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}

Sample Input

4
1 2 3 1 1 1 0
1 2 3 1 1 1 1
1 2 3 1 1 1 2
1 2 3 1 1 1 3

Sample Output

1
2
3
42

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 \times f[2] + 1 \times f[1] + 1 \times f[0] + 3 \times 3 \times (3 + 1)
f[3] = 1+ 2 + 3 + 36
f[3] = 42

Time Limit

5 sec for each test file

If it was simple tribonacci series I would have solved it using companion matrix and matrix exponential method. But how to solve the above problem??

Normally we would use

\begin{bmatrix} f(n-3) & f(n-2) & f(n-1)\end{bmatrix} \times \begin{bmatrix} 0 & 0 & c \\ 1 & 0 & b\\ 0 & 1 & a \end{bmatrix} \\= \begin{bmatrix}f(n-2) & f(n-1) & f(n)\end{bmatrix}

But because we need the values of a 3rd degree polynomial in n, we also need to maintain that

\begin{bmatrix}1 & n & n^2 & n^3 & f(n-3) & f(n-2) & f(n-1) \end{bmatrix}\times\\ \begin{bmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0\\ 0 & 1 & 2 & 3 & 0 & 0 & 0\\ 0 & 0 & 1 & 3 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & c\\ 0 & 0 & 0 & 0 & 1 & 0 & b\\ 0 & 0 & 0 & 0 & 0 & 1 & a \end{bmatrix}\\ = \begin{bmatrix}1 & n+1 & (n+1)^2 & (n+1)^3 & f(n-2) & f(n-1) & f(n)\end{bmatrix}

You just have to use all the neccessary previous values to get a linear recurrence and calculate their coefficients.

2 Likes

did you literally calculate this companion matrix by hand or any procedure you follow, I mean multiplying and getting the values?

Ok so what you want to do is
We have the numbers
\{1,n,n^2 ,n^3, f(n-2), f(n-1),f(n)\}, and we want some linear recurrence such that we get \{1,n+1, (n+1)^2, (n+1)^3, f(n-1), f(n), f(n+1)\}.

A_{ij} = coefficient of the ith value in our initial matrix in the jth value in our final matrix.