### 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*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}

### E1

E_{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]

### E2

E_{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 , 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∗x^{2} + … + f[P-1]∗x^{P-1} )^{2}

Coefficient of x^{i} [ i< P ] is f[0]*f[i]+f1*f[i-1]+…+f[i]*f[0]

Coefficient of x^{i} [ 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 ∑ x^{2}*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 ∑ 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.