Can anyone please explain step by step the approach to solve problem MOREFEB from June Long 2015. asked 15 Jun '15, 18:59

Recursive approach for 40 points Use the identity fib(x_{1}+x_{2}) = fib(x_{1}) * fib(x_{2}+1) + fib(x_{1}1) * fib(x_{2}) For choosing k items from n if you choose any i^{th} index you need to choose another k1 items after i ! For substate i+1 to n for k1 items you will be needing two things : If you already have answers for the range i+1 to n for k1 items then using above identity you can get the result for k items when i^{th} item is choosen at first place ! answered 15 Jun '15, 21:53

I also tried to solve using DP, but managed to score 40 points only. I tried lots of optimisations but nothing helped. As you know fibonacci % mod is a periodic sequence and for mod = 99991, the period = 33330. So if the keys in set are in range 10^{9} we can reduce it to key % 33330 and fibonacci numbers can be computed upto 33330^{th} term easily using simple recurrence fib[n] = fib[n  1] + fib[n  2], without matrix exponentiation because of large values of keys in the set. Then simple recurrence can give the required sum. Consider the Fibonacci Matrix F(n) $$ \left[\begin{array}{cc}F(i  1) & F(i) \\ F(i) & F(i + 1)\end{array}\right]$$ Consider the Solution Matrix Z[n][k] $$ \left[\begin{array}{cc}S(i  1) & S(i) \\ S(i) & S(i + 1)\end{array}\right]$$ So, the recurrence is, Z[k][n] = F[k] * Z[k  1][n  1] + Z[k][n  1]
And Z[k][n & 1][1] is the result. answered 18 Jun '15, 00:40
^could you explain your recurrence?
(18 Jun '15, 07:08)
@ironmandhruv updated the answer.
(18 Jun '15, 09:16)
thanks. answers like these should be added to the editorial. :)
(18 Jun '15, 14:11)

Forget about FFT. Try to understand how to compute answer with recursive function g(l,r). This function returns vector of answers for all K in [0..rl+1] on subarray S[l..r]. You can compute this function with divideandconquer method. To merge results from g(l,mid) and g(mid+1,r ) need just to multiply these vectors as polynomials, this part you need to understand. So, FFT needed only for fast multiplication to achieve better complexity. see my solution answered 15 Jun '15, 19:50
I am not able to understand the divide and conquer approach. Please elaborate a little.
(15 Jun '15, 21:25)
You may see the editorials of following problem for more details about FFT : https://www.hackerrank.com/challenges/emmaandsumofproducts/editorial
(17 Jun '15, 07:54)

DP solution explained here: http://discuss.codechef.com/questions/71544/morefbeditorial/71836 answered 17 Jun '15, 17:52
