PROBLEM LINK:
Author: Devendra Agarwal
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu
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.
Explanation
Free 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*(N-x-y)*T[x,y,z] //x+y+z = N
= ∑ 6*x*y*N*T[x,y,z] - 6*x2*y*T[x,y,z] - 6*x*y2*T[x,y,z] //Follows from previous step
From symmetry of x and y, we can say that
∑ 6*x2*y*T[x,y,z] = ∑ 6*x*y2*T[x,y,z] ,where x+y+z = N
Answer = ∑ 6*x*y*N*T[x,y,z] - 2*∑ 6*x*y2*T[x,y,z]
Let us now bifurcate to solve both expressions individually,i.e.
Let E1 = ∑ 6*x*y*T[x,y,z] , E2 = ∑ 6*x*y*N*T[x,y,z]
Answer = E1*N - 2*E2
E1
E1 =
= ∑ (2*x*y + 2*y*z + 2*z*x)*T[x,y,z] //Reason: symmetry
= ∑ ((x+y+z)2-x2-y2-z2)*T[x,y,z] //Formula of 2*x*y + 2*y*z + 2*z*x
= ∑ (N2 - 3*x2)*T[x,y,z] //Reason: x+y+z= N , and from symmetry of x,y,and z.
= N2*∑ T[x,y,z] - ∑ 3*x2*T[x,y,z]
E2
E2 =
= ∑ 6*x2*y*T[x,y,z]
= ∑ (3*x2*y+6*y2*x)*T[x,y,z] //Symmetry
Using the Identity: (x+y+z)3 = x3 + y3 + z3 + 3*x2*y+6*y2*x + 3*(x+y)*z*(x+y+z) , and also using the fact that x+y+z = N , we get :
= ∑ (N3 - (x3 + y3 + z3 + 3*(xy+yz)*N))*T[x,y,z]
= ∑ (N3 - (3*x3 + 3*(2*x*y)*N)*T[x,y,z] //Symmetry Arguments
= N3* ∑T[x,y,z] - 3*∑ x3*T[x,y,z] - N* ∑ 6*x*y*T[x,y,z]
= N3* ∑T[x,y,z] - 3*∑ x3*T[x,y,z] - N*E1
For calculating E2 , you need E1 , ∑T[x,y,z] and ∑ x3*T[x,y,z]. For calculating E1 , you need ∑ T[x,y,z] and ∑ x2*T[x,y,z].
Overall for calculating answer , all we need is to calculate these three terms : ∑T[x,y,z] , ∑ x2*T[x,y,z] and ∑ x3*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 , you must have realised that the solution is aiming at Order(period of fibo mod M )
Let f denotes the fibonacci series and let P denotes it’s period.
Consider the polynomial G(x):
(f[0] + f1∗x + f2∗x2 + … + f[P-1]∗xP-1 )2
Coefficient of xi [ i< P ] is f[0]*f[i]+f1*f[i-1]+…+f[i]*f[0]
Coefficient of xi [ i ≤ P and i < 2*P ] : f[P-1]*f[i-(P+1)] +…+f[i-(P+1)]*f[P-1]
You can easily find the coefficients in O(N) time instead of using FFT algorithm.
Coefficient[i]=(Coefficient[i+2]-Coefficient[i+1]-f[i+1])mod M for i ≤ P − 3
Try to find out for i>=P.
Now,try to find out the solution to ∑T[x,y,z] using the polynomial.
let al = N mod P , I = N/P , NP = N mod P
for(int i=0;i<P;i++)
z1=Coeficient[al]+Coeficient[al+P]
z2=Coeficient[al];
s = (N-i)/P
ns1 = ( ns1+ f[i]\*z1\*normal(s) )%M; //normal(s) is the series : Sigma(s-t) , t goes from 0 to s-1
ns2=(ns2+f[i]\*z2)
if(i<=NP)
ns3 = (ns3+f[i]\*z2)%M;
al=(al-1+P) % P;
s1 = (s1+s2\*I+s3) % M;
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 ∑ x2*T[x,y,z]
let al = N mod P , I = N/P , NP = N mod P
for(int i=0;i<P;i++)
z1=Coeficient[al]+Coeficient[al+P]
z2=Coeficient[al];
s = (N-i)/P
ss1 = ( ss1+ f[i]\*z1\*square( i , s) )%M; //square(i,s) is the series : Sigma( ((i+t\*p)^2)\*(s-t)) , t goes from 0 to s-1
ss2 = ( ss2+ fz2\*squaring(i,s) ) //squaring(x,s) is x^2 + (x+P)^2 + ....s terms
if(i<=NP)
ss3 = (ss3 + x<sup>2</sup>\*f[i]\*z2)
al=(al-1+P) % P;
ss1 = (ss1+ss2+ss3) % M;
I hope you can find for ∑ x3*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.
Thanks for this