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