### PROBLEM LINK:

**Author:** Andrii Omelianenko

**Tester:** Kevin Atienza

**Translators:** Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)

**Editorialist:** Kevin Atienza

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Recursion, Dynamic programming, meet-in-the-middle

### PROBLEM:

Let f(0) = 1, f(1) = 2 and f(i) = f(i - 1) + f(i - 2) for i > 1. How many ways are there to form the sum X using exactly K summands from the sequence f(0), f(1), f(2), \ldots? Note that summands may be used multiple times, but the summation order doesn’t matter.

### QUICK EXPLANATION:

Let F(x,k,n) be the number of ways to form the sum x using exactly k summands from f(0), f(1), \ldots f(n-1). Then F can be calculated using the following recurrence:

with base case F(x,0,n) = [x = 0]. When implemented as a recursive function, and pruning using the fact that F(x,k,n) = 0 if kf(n-1) < x, this runs very quickly.

### EXPLANATION:

Since order doesn’t matter, it’s best to enumerate the summands in *increasing* order so we don’t count any sum more than once. We will keep this in mind throughout this editorial.

If X is small, then this problem can be solved straightforwardly using dynamic programming. Let’s define F(x,k,n) to be **the number of ways to form the sum x using exactly k summands from f(0), f(1), \ldots f(n-1)**. (We introduced the variable n so that we can perform the DP properly. Finding these hidden variables is usually the trick with DP problems.) The answer that we want is F(X,K,43) because f(42) is the largest f value that is \le 10^9 (the maximum possible value of X).

To find a recurrence for F(x,k,n), notice that there are two cases: whether f(n-1) is in the sum or not.

- If f(n-1) is not in the sum, then x is formed as a sum using exactly k summands from f(0), f(1), \ldots, f(n-2). There are F(x,k,n-1) ways to do that by definition.
- If f(n-1) is in the sum, then the remaining x - f(n-1) is formed using exactly k-1 summands from f(0), f(1), \ldots, f(n-1). (Notice that f(n-1) is still included because duplicate summands are allowed.) By definition, there are F(x-f(n-1),k-1,n) ways to do that.

Altogether, there are F(x,k,n-1) + F(x-f(n-1),k-1,n) ways to form x validly, and we have the recurrence

For base cases, if k = 0, then there are zero summands, so the sum can only be 0. Thus, F(0,0,n) = 1, and F(x,0,n) = 0 if x \not= 0. Also, there are other cases that make F(x,k,n) = 0, like the following:

- k > 0 and x = 0, because having at least one positive summand must result in a positive sum.
- k > 0 and n = 0, because there’s no possible choice of summands left.
- x < 0, because there’s no way to form a negative sum using a finite number of nonnegative summands.

If x is small, like in subtask 3, then this can be used to compute F(x,k,n) for x \le X, k \le K, and n \le 43, and therefore the answer. All we have to do is to **create a 3D table to contain the F(x,k,n) values**, and then **fill it up in the right order.** After doing so, we then have access to the correct value of F(X,K,43). The following pseudocode illustrates this:

```
def compute_answer(X,K):
F[0..X][0..K][0..43]
for x = 0..X:
for k = 0..K:
for n = 0..43:
if k == 0:
if x == 0:
F[x][k][n] = 1
else:
F[x][k][n] = 0
else if x == 0 or n == 0:
F[x][k][n] = 0
else:
F[x][k][n] = F[x][k][n-1]
if x >= f(n-1):
F[x][k][n] += F[x-f(n-1)][k-1][n]
return F[X][K][43]
```

The f(n) values can be precomputed beforehand, so they can be obtained via fast lookups.

The essence of DP is computing a table like this, and the trick is to know what to store and what the variables should be. Usually, the variables aren’t obvious, just like in our case where we added the variable n. Without it, the recursion doesn’t work.

This runs in O(XKN) time, where N is the number of distinct summands we are considering. (In our case, N = 43.) Unfortunately this only works for the third subtask, because for other subtasks, X is too large.

Instead, we’ll describe a few solutions that work even for large X.

# Solution 1

This solution uses the fact that there are only 43 f values that need to be considered, and that K is at most 10. For simplicity of explanation, let’s assume that K = 10. (Other K s have similar approaches.) Also, it uses the fact that a sum of 10 summands can be decomposed into two sums, each containing 5 summands.

The idea is to first **list all possible sums of 5 f values.** How many are there? Using some counting techniques, we find that there are {47 \choose 5} = 1533939, which is quite reasonable. Now the remaining thing is to count **how many ways are there to choose two sums from this list such that the sum is X**. This is solvable with the following algorithm with two pointers:

- Sort all sums of 5 f values. Let this list be [s_1, s_2, \ldots, s_L] where L = 1533939.
- Initialize two pointers, i and j, with i initially pointing at the beginning of the list, and j at the end.
- For each i in increasing order, repeatedly decrement j to find the largest j such that s_i + s_j \le X. If s_i + s_j = X, then increment the answer by one.

Notice that this runs in O(L) because the pointer j never increases, so this passes the time limit for all subtasks. But there are two problems with this:

- We want the summands to be in increasing order. With the algorithm above, this is not necessarily the case. We can fix this by storing the minimum and maximum summand for each s_i, and then only incrementing the answer if the maximum summand for s_i is \le the minimum summand for s_j.
- The $s_i$s are not necessarily distinct. This means that we might need another inner loop to find all j s such that s_i + s_j = X.

Using these adjustments, we now have a solution that runs in reasonable time!

# Solution 2

This solution uses the fact that the f values increase exponentially. Since K is small, it means that inevitably we will need to choose lots of f values that are near to X. Otherwise, we might not be able to achieve X, just because the remaining candidate summands aren’t large enough.

Specifically, the maximum sum we can get from f(0), \ldots, f(n-1) with k summands is k\cdot f(n-1), so if x is larger than that, then F(x,k,n) = 0 automatically. This reduces the amount of F(x,k,n) cases we need to check, and in fact it’s significant enough: With this *pruning*, a normal recursive solution becomes *very* fast!

```
def F(x,k,n):
if k == 0:
if x == 0:
return 1
else:
return 0
else if x == 0 or n == 0:
return 0
else:
total = F(x,k,n-1)
if x >= f(n-1) and x <= k*f(n-1):
total += F(x-f(n-1),k-1,n)
return total
def compute_answer(X,K):
return F(X,K,43)
```