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
agga_daku:
2021-01-31 09:59:44
i am getting wrong answer can anybody help? |
|
ashigup11:
2021-01-16 09:06:31
AC in one go
|
|
coding_sourabh:
2021-01-14 08:47:20
I really wanted to write it atleast once :P , AC in one Go
|
|
codephilic:
2020-09-28 13:36:42
@vimi if we use dp then it will give tle use Matrix Exponentiation concept bcz its time complexity is O(k^3 Logn) |
|
horro:
2020-07-27 21:17:08
Standard Matrix Exponentiation problem!!! |
|
coder_619:
2020-07-20 01:22:09
Ac In 2nd Go.....:) Last edit: 2020-07-20 01:23:31 |
|
rohitkk074:
2020-06-25 09:54:44
@abhi i made the same mistake, was doing % (1e9+7)
|
|
abhj:
2020-06-25 00:52:12
1e9 modulo kaun karta hai? Debug karne main adha ghanta chala gaya |
|
souravbhadra03:
2020-06-15 07:55:06
Accepted
|
|
cs215100:
2020-05-20 21:35:01
tle in java. same code ac in c++. |
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 |