PROBLEM LINK:Author: Devendra Agarwal DIFFICULTY:Hard. PREREQUISITES:Mathematics. PROBLEM:Find the value for the expression ∑ (6*x*y*z*Fibo[x]*Fibo[y]*Fibo[z]) where x+y+z = N. ExplanationFree Advice: Please sit with a pen/pencil and a copy to grasp the solution for the problem. We will denote Fibo[x] with F[x] , and T[x,y,z] = Fibo[x]*Fibo[y]*Fibo[z] in the whole editorial. = ∑ 6*x*y*z*T[x,y,z] = ∑ 6*x*y*(Nxy)*T[x,y,z] //x+y+z = N = ∑ 6*x*y*N*T[x,y,z]  6*x^{2}*y*T[x,y,z]  6*x*y^{2}*T[x,y,z] //Follows from previous step From symmetry of x and y, we can say that ∑ 6*x^{2}*y*T[x,y,z] = ∑ 6*x*y^{2}*T[x,y,z] ,where x+y+z = N Answer = ∑ 6*x*y*N*T[x,y,z]  2*∑ 6*x*y^{2}*T[x,y,z] Let us now bifurcate to solve both expressions individually,i.e. Let E_{1} = ∑ 6*x*y*T[x,y,z] , E_{2} = ∑ 6*x*y*N*T[x,y,z] Answer = E_{1}*N  2*E_{2} E1E_{1} = = ∑ (2*x*y + 2*y*z + 2*z*x)*T[x,y,z] //Reason: symmetry = ∑ ((x+y+z)^{2}x^{2}y^{2}z^{2})*T[x,y,z] //Formula of 2*x*y + 2*y*z + 2*z*x = ∑ (N^{2}  3*x^{2})*T[x,y,z] //Reason: x+y+z= N , and from symmetry of x,y,and z. = N^{2}*∑ T[x,y,z]  ∑ 3*x^{2}*T[x,y,z] E2E_{2} = = ∑ 6*x^{2}*y*T[x,y,z] = ∑ (3*x^{2}*y+6*y^{2}*x)*T[x,y,z] //Symmetry Using the Identity: (x+y+z)^{3} = x^{3} + y^{3} + z^{3} + 3*x^{2}*y+6*y^{2}*x + 3*(x+y)*z*(x+y+z) , and also using the fact that x+y+z = N , we get : = ∑ (N^{3}  (x^{3} + y^{3} + z^{3} + 3*(xy+yz)*N))*T[x,y,z] = ∑ (N^{3}  (3*x^{3} + 3*(2*x*y)*N)*T[x,y,z] //Symmetry Arguments = N^{3}* ∑T[x,y,z]  3*∑ x^{3}*T[x,y,z]  N* ∑ 6*x*y*T[x,y,z] = N^{3}* ∑T[x,y,z]  3*∑ x^{3}*T[x,y,z]  N*E_{1} For calculating E_{2} , you need E_{1} , ∑T[x,y,z] and ∑ x^{3}*T[x,y,z]. For calculating E_{1} , you need ∑ T[x,y,z] and ∑ x^{2}*T[x,y,z]. Overall for calculating answer , all we need is to calculate these three terms : ∑T[x,y,z] , ∑ x^{2}*T[x,y,z] and ∑ x^{3}*T[x,y,z]. Let us try to solve ∑T[x,y,z] : First off all , you should write a small code to find the pisano period of all numbers from 1 to 100000, you will note that the maximum pisano period is 375000. Maximum value of Period / M <= 6. Now,try to find out the solution to ∑T[x,y,z] using the polynomial.
s1 contains the value of ∑T[x,y,z]. You need to start from small N and M , try to find the pattern and code it.You may find the pseudo code to be beneficial. For solving the other two version , it is quite straight forward from here. You will get a different series to solve in both cases and the overall structure remains almost the same. Below is the pseudo code for ∑ x^{2}*T[x,y,z]
I hope you can find for ∑ x^{3}*T[x,y,z] yourself. I saw some awesome solutions , I would like to invite every participant to share their awesome ideas with us :) . Complexity: O(period) per test case = O(M) per test case. AUTHOR'S and TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 11 Aug '14, 15:13

Awesome problem!!! I guess there can be a lot of ways to solve this problem. In my case I derived a formula for the nth term by solving set of simultaneous equations of 12 variables taking a clue from this paper: http://www.mathstat.dal.ca/FQ/Scanned/152/hoggatt1.pdf F(N) = ∑ (6xyzFibo[x]Fibo[y]Fibo[z]) = ((5N^5 + 35.N^3  4.N).Fibo(N)  36.N^2.Lucas(N))/500 The problem with the above approach was that for M which have factors which are powers of 2 and 5, mod inverse of 500 does not exist. For these cases I used a different approach, the idea again from the same paper. I used the recurrence relations for the rth Fibonacci convolution sequences. I precomputed 5th Fibonacci convolution sequence for the highest powers of 2 and 5 possible. The generating function for the 5th Fibonacci convolution sequence is (x/(1xx^2))^6, whereas our sequence has a generating function of 6.(x.(1+x^2)/(1xx^2)^2)^3 or 6.(x^3 + 3.x^1 + 3.x^1 + x^3).(x/(1xx^2))^6. So we can obtain F(N) from the 5th Fibonacci convolution sequence by using the formula F(N) = 6. (F5(N3) + 3.F5(n1) + 3.F5(N+1) +F5(N+3)) , where F5(N) is the 5th Fibonacci convolution sequence as precomputed above. Finally, to address how we arrived at the generating function of our sequence, we notice that our function is the result of convolution of the sequence N.Fibo(N) with itself 2 times. Generating function of the sequence N.Fibo(N) is the first derivative of the Fibonacci sequence shifted by 1 position whose generating function is x/(1xx^2) and hence has a generating function x.(1+x^2)/(1xx^2)^2 Hence the generating function for our sequence is 6 times the cube of this as we are convolving 2 times. answered 11 Aug '14, 16:43
I went the same route but got stuck on the case where M % 2 ==0  M % 5 == 0 Could you please provide the link of your solution?
(11 Aug '14, 18:56)
2
omg awesome explanation!!! I really get blown away by how truly talented some people are...and even though I'll never reach this level, just having the chance to learn a few things is already awesome for me :D Thanks for this
(11 Aug '14, 20:19)
1
I got the generating function, and I found a 12th order recursion that described the sequence. Sadly, I couldn't do necessary matrix multiplications within the time limit. Alas, it seemed like a decent approach at the time.
(12 Aug '14, 07:04)
Great work ^_^ I was going for this problem, did a bit of mathematics but other problems took a lot of time. A good way to learn, Thanks :D
(12 Aug '14, 14:42)

Here's my approach (first look at my solution here: http://www.codechef.com/viewsolution/4502528 ). It seems I'm pulling a lot of numbers out of nowhere, so I'll try to why all these numbers appear. The first step I did was try to find a generating function for this sequence. This is because it is very likely to correlate to a recurrence, and if we have a recurrence, we can get the Nth term in log N time using matrix exponentiation (if you know how to compute fib(n) in log n time, then this will kind of explain how to do this). So, let's try to find the generating function. As @n2n_ has already pointed out, the generating function for this sequence is (x(x^2+1) / (1xx^2)^2)^3 (read his explanation on how to derive it, I pretty much did the same thing). Now knowing how to convert generating functions into a recurrence is very useful. In general, if a sequence a(n) has generating function 1/p(x) where p(x)=1  c1 * x  c2 * x^2  ...  ck * x^k, then the corresponding recurrence is a(n) = c1 * a(n1) + c2 * a(n  2) + ... + ck * a_(nk). Now, what about sequences with generating functions of the form q(x)/p(x). Well, let's say q(x) = b0 + b1x + b2x^2 + ... + bm x^m. Then, if we have already derived a(n) above from just 1/p(x), our actual value of the nth term a'(n) = b0 a(n) + b1 a(n  1) + ... + bm a(nm). Thus, we have a general form for the recurrence given that the numerator and denominator are polynomials, which they luckily are. We fully expand these out, to get the recurrence relationship as described above. This recurrence will have each term rely on the 12 terms before this. As for the values of a(0) to a(11), we can brute force the taylor expansion of 1/p(x) to get these. Thus given the recurrence, we can solve each case in log N time. This is the basic idea of my solution, but I had some trouble getting this to just pass because of a constant factor, so I did some optimizations (pre computing some periods) to get it to eventually pass. answered 11 Aug '14, 21:47
6
If you use CayleyHamilton theorem, you could replace matrix multiplication by polynomial multiplication, which will give a 12X speedup in this case.
(11 Aug '14, 22:16)
Thanks for the tip! I'll be sure to read up on that when I have more time since I don't quite understand that now.
(11 Aug '14, 22:32)
@djdolls, I've been thinking on how to use CayleyHamilton Thm to obtain the speedup, but couldn't find out. Could you explain how you would do it? Thanks!
(14 Aug '14, 03:42)
I'll try to explain. Let's try to motivate this first. Suppose we have a matrix A and we want to find A^1000. Suppose we also know that p(A) = 0 for some polynomial p. To demonstrate, let's suppose p(A) = A^2  2A + 1 = 0. Now, we know A^1000  2A^999 + A^998 = 0, so A^1000 = 2A^999  A^998. Then, we can write A^999 and A^998 in terms of smaller powers and so on until we just get things in terms of A^1, and 1. Now, this is much easier to evaluate, and is very fast (a 12x speedup in this case). Now, how do we find this characteristic polynomial? We just use the CayleyHamilton theorem.
(14 Aug '14, 07:00)
Do you have references to learn how to convert generating functions to recurrence relations? I asked in SE.math but got no answer.
(14 Aug '14, 09:17)
I have a simple, but manual, way of doing it. I'll make an example with the fibonacci generating function. First put the GF in that form: p(x)/(1f(x)), so: 1/(1(z+z^2)). The recurrence relation is pretty simple now: a[n]=a[n1]+a[n2], had it been 3x/(1(z+2z^2+3z^3)) it would have been a[n]=a[n1]+2a[n2]+3a[n3]. Put the GF in wolframalpha to do the Taylor expansion and obtain the first terms, in the fibonacci series you would obtain: 1+z+2z^2+... so first terms would be a[0]=1,a[1]=1.
(14 Aug '14, 14:17)
In case you don't have access to internet you will have to play a little bit: p(x)/(1f(x)) = GF(x) try to guess the first coefficients of GF(x) so that when you multiply if by (1f(x)) you get p(x).
(14 Aug '14, 14:17)
@lg5293 wouldn't your algorithm be O(n)? Sure the constant would be smaller but in this case n=10^18.
(14 Aug '14, 14:21)
please see http://discuss.codechef.com/questions/49614/linearrecurrenceusingcayleyhamiltontheorem I have explained how to use CayleyHamilton theorem to solve linear recurrence faster than matrix exponentiation method.
(14 Aug '14, 16:05)
nice explanation, thanks!
(15 Aug '14, 05:32)
showing 5 of 10
show all

http://pan.baidu.com/s/1sjqGiDn this is how i solve it（chinese） answered 11 Aug '14, 17:14

May be noob question. Can someone please explain the second decomposition in calculating E2? i.e. how sigma(6x2yT[x,y,z]) = sigma((3x2y+6y2x)T[x,y,z]) answered 18 Aug '14, 08:02

Access denied in testers soln.
May be noob question. Can someone please explain the second decomposition in calculating E2? i.e. how sigma(6x2yT[x,y,z]) = sigma((3x2y+6y2x)T[x,y,z])