@ash_code can be solved using golden ratio … check this
[1]
check the last comments of [this][2].
[1]: https://www.codechef.com/viewsolution/9837297
[2]: http://codeforces.com/blog/entry/18292I used the golden ratio and the polynomial multiplication approach https://www.codechef.com/viewsolution/9838337
2 Likes
There is one more optimization which should work for computing fibonacci. For modulus 10^9+7, pisano number was 2*10^9+18. So if number greater than this, we first take modulus with 2 * 10^9 + 18 and then compute Fibonacci.
It would be great if you can explain me how the multisets are generated of each interval in the segment tree from Fibo(A+B)?
4 Likes
The problem could be made more challenging by introducing range update 
I also I don’t find the relationship between Fibonacci(n+m) and F(A U {x}) intuitive at all. Does anyone have a justification of this, other than ‘clearly’ or ‘notice’ or ‘easily see’?
Please mention the topics or Algorithms along with the links that are required as a prerequisite for this problem…
Can anyone explain this editorial in an easy language…that is understandable to a newbiee…
Thanks in advance (y)
2 Likes
Here is a decent intro to segment trees: Segment Tree | Sum of given range - GeeksforGeeks
Here is a reference I used for Fibonacci generation: fedelebron.com - Fast modular Fibonacci
Hope that helps, though I think there is a little bit of mystery that noone has explained linked to regarding this particular function (not prereqs).
Can some one explain how CombineIntervalInfo() generates multiset as well as the summation.
Thanx in advance.
whole time i was figuring out how can we get all subset of the set… as to me that was the main problem… but after contest ended i came to know of -> (1+a)(1+b)(1+c)…(1+n)=1 + (all__subset__in__product__form)… eg. (1+a)(1+b)(1+c)=1+a+b+c+ab+bc+ca+abc…
as u can see now we just can now easily use segment tree…
Consider a segment tree “tree” where all nodes hold some matrix. Like I said in my previous comment, let us store in the leaf node, M^x where x is the corresponding element and M = [[1,1],[1,0]].
Now for a node which is not a leaf, we simply need tree + tree[right] + tree.tree[right], where left and right are the left and right child respectively. We keep doing this recursively and build the segment tree.
Now for updating, we will update only one element and not a range. So we update a leaf node, and make sure to update all the ancestors of this leaf node. In other words, we are rebuilding the segment tree for every update. Also note, after using the array element initially to build the segment tree, the array is not needed anywhere else in the code. So actually when updating the array, we can only update the segment tree because all further computations will be held by the segment tree.
For query, I followed the basic segment tree propagation method (not lazy) to create a dummy matrix which will hold the data for the range query. This matrix will contain the final result. We only output the [1][0] element of this matrix. For further details, please read my code here and my earlier post. Cheers!
let array= [n1,n2,n3…nn];
A=(1+sqrt(5))/2 and B=(1-sqrt(5))/2
thus from a derivation i found Sum of all fibonacci multiset is=> 1/sqrt(5)*[(1+A^n1)(1+A^n2)…(1+A^nn)-(1+B^n1)(1+B^n2)…(1+B^nn)]
with this fetch takes O(1) time.
because:suppose x1=(1+A^n1) and y1=(1+A^n1) similarly x2=(1+A^n1)(1+A^n2) and y2=(1+B^n1)(1+B^n2).
Thus if we make an array of x and y such as
X=[x1,x1x2,x1x2x3,x1x2x3x4, to xn] and
Y=[y1,y1y2,y1y2y3,y1y2y3y4, to yn]
thus for Q 1 5 we take (X5-Y5)/sqrt(5); thus happens in O(1) time. And to build this array we take O(n) time… I want to know why this approach is not suitable here??? I have no clue whatsoever!!! I was getting wrong ans for this. I used long double for storing all double values!! can some one help??
could someone pls explain the reasoning/intuition behind the combineIntervalInfo() routine.
can anyone explain what we store in the node.sfibm1 and node.sfibp1 of a non-leaf node? I am able to understand what we store in node.sfib… but can’t able to understand the other two values stored… plz reply…
Can this be solved using the golden ratio?
To partially answer your question: the interval multisets are not generated, it’s not necessary. CombineIntervalInfo will calculate the correct answer, but I don’t understand how. Specifically I don’t understand how “F(A+B) = F(A).F(B+1) + F(A-1).F(B)” can be applied to Sum(F(Sum(s))) for s in multisets.
Here is an example where I computed the combination of [3, 4] and [1,2] and then [3, 4, 1, 2] separately, just to confirm it works: https://i.imgur.com/UwakZCg.jpg
Can anyone explain how they are finding the sum of individual subsets in a given range?
please give link to your code