PIBO - Fibonacci vs Polynomial
Define a sequence Pib(n) as following
- Pib(0) = 1
- Pib(1) = 1
- otherwise, Pib(n) = Pib(n-1) + Pib(n-2) + P(n)
Here P is a polynomial.
Given n and P, find Pib(n) modulo 1,111,111,111.
Input
First line of input contains two integer n and d (0 ≤ n ≤ 109, 0 ≤ d ≤ 100), d is the degree of polynomial.
The second line contains d+1 integers c0, c1 … cd, represent the coefficient of the polynomial (Thus P(x) can be written as Σcixi). 0 ≤ ci ≤ 100 and cd ≠ 0 unless d = 0.
Output
A single integer represents the answer.
Example
Input: 10 0 0 Output: 89
Input: 10 0 1 Output: 177
Input: 100 1 1 1 Output: 343742333
hide comments
David:
2021-09-29 22:44:26
Trapped by slow Java again! |
|
Problem Solver:
2011-11-12 01:16:02
Oh, yes, sorry for that |
|
Miguel Oliveira:
2011-11-12 01:07:38
The answer is 89. Note that Pib(n) is not the same as the Fibonacci sequence as Pib(0)=1 while Fib(0)=0
|
|
Problem Solver:
2011-11-12 00:35:25
Hey @Bin Jin
|
Added by: | Bin Jin |
Date: | 2011-11-11 |
Time limit: | 1s |
Source limit: | 10240B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 CPP |