Recurrence Solver

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 16M

Problem type

A linear homogeneous recurrence relation of order $d$ $d$ with constant coefficients has the seed values $t_0, t_1, \dots, t_{d-1}$ $t_{0}, t_{1}, \dots, t_{d - 1}$ with further terms defined according to $t_n = c_1 t_{n-1} + c_2 t_{n-2} + \dots + c_d t_{n-d}$ $t_{n} = c_{1} t_{n - 1} + c_{2} t_{n - 2} + \dots + c_{d} t_{n - d}$ . For example, let $d = 2$ $d = 2$ . This means that the first two terms $t_0$ $t_{0}$ and $t_1$ $t_{1}$ have specified values. Let $c_1 = c_2 = 1$ $c_{1} = c_{2} = 1$ , then all terms $t_n$ $t_{n}$ for $n > 1$ $n > 1$ are defined as $t_n = t_{n-1} + t_{n-2}$ $t_{n} = t_{n - 1} + t_{n - 2}$ . When $t_0 = 0$ $t_{0} = 0$ and $t_1 = 1$ $t_{1} = 1$ , the sequence begins $0, 1, 1, 2, 3, 5, 8, \dots$ $0, 1, 1, 2, 3, 5, 8, \dots$ : the Fibonacci sequence.

Given the values of $d, t_0, \dots, t_{d-1}$ $d, t_{0}, \dots, t_{d - 1}$ , and $c_1, \dots, c_d$ $c_{1}, \dots, c_{d}$ and a non-negative integer $n$ $n$ , can you determine the term $t_n$ $t_{n}$ in this sequence, modulo $10\,007$ $10 007$ ?

Input Specification

The first line of input contains two integers separated by a space, $d$ $d$ $(0 < d \le 50)$ $(0 < d \leq 50)$ and $n$ $n$ $(0 \le n < 10^9)$ $(0 \leq n < 10^{9})$ .
Each of the following $d$ $d$ lines contains one integer $t_i$ $t_{i}$ $(-10\,000 < t_i < 10\,000)$ $(- 10 000 < t_{i} < 10 000)$ . They are given in the order $t_0, t_1, \dots, t_{d-1}$ $t_{0}, t_{1}, \dots, t_{d - 1}$ .
Each of the following $d$ $d$ lines contains one integer $c_i$ $c_{i}$ $(-10\,000 < c_i < 10\,000)$ $(- 10 000 < c_{i} < 10 000)$ . They are given in the order $c_1, c_2, \dots, c_d$ $c_{1}, c_{2}, \dots, c_{d}$ .

Output Specification

Output a single line containing $t_n \bmod 10\,007$ $t_{n} mod 10 007$ .
Note that although the mod operator in your language may give negative results, the answer should be a non-negative integer.

Sample Input

Copy

2 10
2 1
1 1

Sample Output

Copy

Explanation

This sequence is defined according to $t_0 = 2, t_1 = 1$ $t_{0} = 2, t_{1} = 1$ , and $t_n = t_{n-1} + t_{n-2}$ $t_{n} = t_{n - 1} + t_{n - 2}$ where $n > 1$ $n > 1$ . This is the sequence of so-called Lucas numbers, beginning $2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123$ $2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123$ . (This question was also used in the PEG short questions homework packages.)

Comments

1

cabbagecabbagecabbage commented on Dec. 29, 2020, 8:17 p.m.

the integers after the first line appear as 1 on each line for 2*d lines as the input specification states, not space separated as the sample input shows. irrelevant to c++ input but slightly misleading for me when I tried to do this with python.