MOREFB - Editorial

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.

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

Explained in this answer:

great explanation!
should be added to the editorial!

Thanks! Note that this solution is O(nk) and thus only gets 40 pts

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