FINDLR - Find Linear Recurrence
You are given the first $2K$ integers $a_0, a_1, \ldots, a_{2K-1}$ (modulo $M$) of an infinite integer sequence $(a_i)_{i=0}^{\infty}$ that satisfies an integer-coefficient linear recurrence relation of order $K$.
That is, they satisfy $$ a_n = \sum_{i=1}^{K} c_i a_{n-i} $$ for $n \ge K$, where $c_1, \ldots, c_K$ are integer constants.
Find $a_{2K}$ modulo $M$.
Input
The first line contains $T$ ($1 \le T \le 4000$), the number of test cases.
Each test case consists of two lines:
- First line contains $K$ ($1 \le K \le 50$) and $M$ ($1 \le M < 2^{31}$).
- Next line contains $2K$ integers $a_0, a_1, \ldots, a_{2K-1}$ (modulo $M$).
Note: $M$ is not necessarily a prime.
Output
For each test case, output $a_{2K}$ modulo $M$.
Example
Input
6 1 16 4 8 1 10 4 8 2 64 13 21 34 55 2 27 13 21 7 1 3 1000000007 32 16 8 4 2 1 2 64 13 21 34 56
Output
0 6 25 8 500000004 40
hide comments
userhacker_1:
2018-03-14 07:45:42
@min_25 --> it was better you give tutorial for your problems(all) or give some article about knowledge of solving your problems! Last edit: 2018-03-15 10:36:25 |
|
Min_25:
2018-01-01 05:22:03
@zimpha: Thank you! |
|
zimpha:
2017-12-31 16:28:25
@Min_25 Very nice problem! |
|
Min_25:
2017-12-16 12:38:14
@Scape: Each c_i is an integer. So, there are no such cases. |
|
Scape:
2017-12-16 12:28:39
If M is not a prime, sometimes there might be no solution.
|
|
Min_25:
2017-10-21 02:39:05
@Blue.Mary
|
|
[Rampage] Blue.Mary:
2017-10-21 02:15:04
I'm not sure if this problem coincide with this one:
|
Added by: | Min_25 |
Date: | 2017-10-20 |
Time limit: | 5s-15s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |