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
jaybatra:
2020-05-02 18:48:59
can someone explain when I used python 3 it gives TLE but when i used C++ using same logic of matrix exponentiation it passed all the test cases why? |
|
jaybatra:
2020-05-01 10:46:53
I have tried the question using python 3 it is passing the given examples but at the time of submitting it is giving TLE can someone help? |
|
vimi:
2020-04-25 20:36:32
can we apply DP with some memoization? because surely we have overlapping subproblems |
|
jainaagam96:
2020-04-24 20:41:29
i tried threw Python 3 (matrix exponentiation ) But,Giving me TLE |
|
fighter_4:
2020-04-12 07:53:24
accepted,:D |
|
hellb0y_suru:
2020-02-19 15:38:33
Matrix exponentiation !!!
|
|
lm10_piyush:
2020-02-15 16:37:11
damn hogya!!! if is allowed to provide the solution like here I can post it...
|
|
harish_49:
2019-11-03 12:37:34
AC in 0 go !!! Nice problem |
|
devinamuljono:
2019-10-19 09:58:23
manage to get accepted after dealing with some edge case , |
|
saifu:
2019-10-13 09:38:06
I am getting segmentation fault for 3rd test case. Please help me. |
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 |