PIBO2 - Fibonacci vs Polynomial (HARD)
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.
Maybe you should solve PIBO before this task, it has lower constraints.
First line of input contains two integer n and d (0 ≤ n ≤ 109, 0 ≤ d ≤ 10000), 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 < 1,111,111,111 and cd ≠ 0 unless d = 0.
A single integer represents the answer.
Input: 10 0 0 Output: 89 Input: 10 0 1 Output: 177 Input: 100 1 1 1 Output: 343742333
I've learnt so many things to tackle this one (even though I haven't used all of them)... Beautiful problem :)Last edit: 2014-11-18 19:40:07
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
Last Position! :p
Hrm, this seems pretty hard. I thought with a 0.01s runtime in PIBO and O(d) memory it'd be good enough, but apparently it's not :s
It was great to solve this hard edition, I did my best with O(d) memory print. ;-)