Submit | All submissions | Best solutions | Back to list |
SEQ - Recursive Sequence |
Sequence (ai) of natural numbers is defined as follows:
ai = bi (for i ≤ k)
ai = c1ai-1 + c2ai-2 + ... + ckai-k (for i > k)
where bj and cj are given natural numbers for 1 ≤ j ≤ k. Your task is to compute an for given n and output it modulo 109.
Input
On the first row there is the number C of test cases (equal to about 1000).
Each test contains four lines:
k - number of elements of (c) and (b) (1 ≤ k ≤ 10)
b1 ... bk - k natural numbers where 0 ≤ bj ≤ 109 separated by spaces
c1 ... ck - k natural numbers where 0 ≤ cj ≤ 109 separated by spaces
n - natural number (1 ≤ n ≤ 109)
Output
Exactly C lines, one for each test case: an modulo 109.
Example
Input: 3 3 5 8 2 32 54 6 2 3 1 2 3 4 5 6 6 3 24 354 6 56 57 465 98765432 Output: 8 714 257599514
Added by: | Paweł Dobrzycki |
Date: | 2005-04-29 |
Time limit: | 0.5s-3s |
Source limit: | 8196B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | IV Podlasian Contest in Team Programming |
hide comments
|
||||||||
2018-08-14 23:10:21
though concept is easier to think but implementation took me hours |
||||||||
2017-12-26 16:41:57
when to take mod |
||||||||
2017-08-22 19:43:16
How can output of 3rd case be 257599514, this number is greater than 1e9 and so by modulo the output must be 57599514. Where am I going please help.. |
||||||||
2016-08-06 13:56:12 Rajat Sharma
Java: will learn matrix exponentiation with recursion, linear recursive equations, how to solve these equations by converting the addition into multiplicative expressions i.e. through matrices. |
||||||||
2016-03-07 15:56:45 Deepak Singh Tomar
matrix_exponentiation. Thanks fushar :) |
||||||||
2016-02-03 17:26:12 minhthai
be careful the mod is 10^9 not 10^9 + 7 :) |
||||||||
2015-08-27 18:45:42 Ðức Tân
dễ vãi |
||||||||
2015-06-25 07:28:24
Hint: While doing matrix multiplication, DON'T do temp[][] += mod(F[][] * M[][]); instead do temp[][] = mod(temp[][] + F[][] * M[][]) costed me 3 WA's ... phew... best of luck |
||||||||
2015-05-30 15:59:01 i_am_looser
learnt something new.......... ; ) |
||||||||
2015-03-11 17:52:35 sai krishna
ha ha ha lot of fun in doing it:) |