MOREFB - Editorial

Interesting thing to know about Fibonacci numbers is that when we take mod with 99991 the Fibonacci cycle repeats itself after length of 33330 which can be verified here http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html#section6.1

1 Like

Can anyone please explain the last part i.e. Also, if K were 2, then the answer would have been F3 whose g(b) would be the coefficient of x0

I propose an alternate solution:

We can prove by induction that the matrix:

[1 1]
[1 0]

raised to the n-th power gives

[F_n+1 F_n  ]
[F_n   F_n-1]

Let’s call the matrix M, for short.

We should easily figure out that
F_(a+b) is the top-right (or bottom-left) element of M^a * M^b

Then how can we use this to out advantage?

Well, if we dive deeper into this statement, we can argue that F_sum(V), over any V, is the top-right cell of the matrix product(M^V[i]).

Also, from M^a + M^b we can translate easily to F_a + F_b (we just take the element I recalled);


Let’s summarize:

  • M^a + M^b <-> F_a + F_b
  • M^a * M^b <-> F_(a+b)

then SUM of F_(SUM of elements) can be translated to SUM of PRODUCT of corresponding matrices.

Let’s continue.

If we take all subsequences of cardinality K, then FIBOSUM(k) is the sum of all PRODUCT(M^v[i]), for each v subsequence of V of cardinality K. If we further analyze this, by the rule of Viete, it turns out to be the (N-K)th term of the polynom P(X) = PRODUCT(X + M^V[i]), for i = 1,n. Basically, we have to find out the (matrix) coefficients of the polynom P(X), which can be done with divide et impera and FFT or Karatsuba (gave me TLE).

Why would this be better? Well, it’s not. For this case at least. However, it does work in any case, no matter how the modulo is chosen.

4 Likes

I waited two days for this editorial hoping to find a good FFT explanation relevant to this question, and examples.

Why TL is so huge? Karatsuba version passed in 0.8 sec.

Editorial is not clear. Please explain the FFT part.

I learned fft from a very well written article, which is very friendly and not so hectic:

After understanding this, you can try reading some more papers and more easily feel for it.
Google is our friend on this one!

When for S=1,2, it was coefficient in (x+b^a1)(x+b^a2)…
then from where did the term (x-b^a1) come in generalization??? shouldn’t it be (x+b^a1) or you should have explained that too… please reply soon

Here is the DP approach that I used to solve this for 40 pts.

We notice that we need to evaluate sums of the form f(a + b) + f(b + c) + f(a + c). So we’ll go to Wolfram’s Fibonacci Numbers page to find a formula that might help us solve this problem. Scrolling down the page (and admiring the beauty of Fibonacci numbers), we stumble across this cute formula:

F_{m+n} = \frac{1}{2}(F_mL_n + L_mF_n)
where L_n is the n^{th} Lucas number (the Lucas series have the same recurrence as Fibonacci but different initial values).
But how do we deal with the L_n terms? Simple, another formula at the Lucas number page says,

L_{m+n} = \frac{1}{2}(5F_mF_n + L_mL_n)

The n^{th} Lucas number can be found in the same way as Fibonacci numbers in O(\log n) time with matrix exponentiation.
So we now have found a way to build the FIBOSUM(s) values as we consider more and more elements in S. Let’s define FS(n, k) as FIBOSUM(S[1..n]) for subsets of k cardinality. We also define LS(n, k) similarly with the Fibonacci function replaced by the Lucas function.

We will form the recurrence in the lines of \binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1} which is formed by considering the two cases of A) not taking the n^{th} element and B) taking it.

The recurrence for FS(n, k) is a sum of two components, first being FS(n - 1, k) where we do not take the n^{th} element. The second is the sum,

\displaystyle\sum_{i=1}^{t} F_{S[n]+m_i} if FS(n - 1, k - 1) = \displaystyle\sum_{i=1}^{t} F_{m_i}

which is equivalent to,

\frac{1}{2}(F_{S[n]}(\displaystyle\sum_{i=1}^{t} L_{m_i})+L_{S[n]}(\displaystyle\sum_{i=1}^{t} F_{m_i})) = \frac{1}{2}(F_{S[n]}LS(n - 1, k - 1)+L_{S[n]}FS(n - 1, k - 1))

The final recurrence becomes,

FS(n, k) = FS(n - 1, k) + \frac{1}{2}(F_{S[n]}LS(n - 1, k - 1)+L_{S[n]}FS(n - 1, k - 1))

LS(n, k) = LS(n - 1, k) + \frac{1}{2}(5F_{S[n]}FS(n - 1, k - 1)+L_{S[n]}LS(n - 1, k - 1))

FS(1, 1) = F_{S[ 1 ]}

LS(1, 1) = L_{S[ 1 ]}

Following is the pseudocode,

FS[1][1] = fib(a[1]);
LS[1][1] = luc(a[1]);
LS[1][0] = 2; //luc(0) = 2
for i = 2 to N
{
	LS[i][0] = 2; //luc(0) = 2
	for j = 1 to K
	{
		FS[i][j] = (FS[i-1][j-1] * luc(a[i]) + LS[i-1][j-1] * fib(a[i])) / 2 + FS[i-1][j];
		LS[i][j] = (5 * FS[i-1][j-1] * fib(a[i]) + LS[i-1][j-1] * luc(a[i])) / 2 + LS[i-1][j];
	}
}

Note that all operations in the pseudocode above are under mod 99991.

Solution link

2 Likes

How do you get the values of a,b and c?

Would be interesting to know if it can be solved for 100pts with matrix multiplication.

I solved 2 subtasks(40pts) with a DP solution and matrix exponentiation, if you’re interested: CodeChef: Practical coding for everyone

@bbackspace, can you explain your approach a little bit, specially that lucas number part.

Hey, how did you calculate a and b? I don’t know what concept is used here. Please give me a link , if you have so I can read in detail.

@filmwalams you might have to read up on solving linear recurrences. Here’s a good link for the Fibonacci sequence specifically: http://gozips.uakron.edu/~crm23/fibonacci/fibonacci.htm. The idea is that the characteristic polynomial factors nicely mod 99991:

$(x - 55048)(x - 44944) = x^2 - 99992x + 2474077312 = x^2 - x - 1 (mod 99991)$.

Yes, it happens after Pisano period.

You may see the editorials of following problem for more details : Emma and sum of products | HackerRank

1 Like

You may see the editorials of following problem for more details about FFT : Emma and sum of products | HackerRank

1 Like

Can it be of any use in this question?? Or do you know any question which uses this property

I wrote Karatsuba with matrices as a coefficients, and my first implementation was running 4 minutes :slight_smile:

Had to spend some time to improve it down to 3.5 seconds :slight_smile:

I don’t think it is bad to have such a huge TL, unless naive solutions can pass.