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
mostafa_188:
2024-06-06 21:26:23
Accepted after tried 13 times. I am not alien that i can solve this in one go. |
|
twoam:
2024-05-03 08:54:26
mod is okay, but the ordering is confusing. i expected a(n+1) to be b1*c1+b2*c2+...
|
|
sakshamshri:
2024-01-05 15:49:22
accepted in 3rd attempt....actually i didnt notice that mod = 1e9 , earlier i used 1e9+7, so guys take care of mod Last edit: 2024-01-05 15:49:55 |
|
tanish_29:
2023-02-11 05:45:59
If you're coding in Java and are struggling with mod, I used long instead of int and then used modulus and it worked for me. Last edit: 2023-02-11 05:47:44 |
|
coutaditya:
2021-12-23 15:42:33
Accepted in one go :) |
|
terminator0309:
2021-07-19 11:03:18
here MOD is 1e9 not 1e9+7 |
|
blueflare99:
2021-06-08 11:07:10
Guys don't fear about fixing %MOD while doing matrix multiplication. It will remain like this only:
|
|
jaydip001:
2021-05-16 12:22:28
At last solved the excellent question |
|
terminator2001:
2021-04-10 15:15:28
bc
|
|
maheshwari7778:
2021-03-20 09:24:20
Amazing blog
|
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 |