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
hide comments
davemaharshi7:
2019-10-04 16:48:37
Anybody here after Coding Blocks tutorial on this ... |
|
neerajamoniya:
2019-09-26 08:20:01
Why is recursion giving TLE ???? |
|
divyanshu12312:
2019-08-06 14:05:59
Long Implementation
|
|
smiling_addu:
2019-07-28 05:59:57
WA in one go.... :) |
|
maratha:
2019-07-26 19:14:21
You might find problem 'Retrospective Sequences' on codeforces gym similar to this.(Slight variation) Last edit: 2019-07-26 19:15:33 |
|
sagar_june97p:
2019-06-12 14:07:21
AC in One go!!! |
|
surajk543:
2018-10-19 14:05:29
Got Accepted Finally...YAAHOOOO>>> |
|
masterchef2209:
2018-09-07 23:30:45
AC in 1 go
|
|
riyuzaki251097:
2018-08-14 23:10:21
though concept is easier to think but implementation took me hours
|
|
hrsh_sengar:
2018-03-14 09:06:48
My 100th :)
|
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 |