PROBLEM LINK:Author: Andrii Omelianenko DIFFICULTY:EasyMedium PREREQUISITES:Recursion, Dynamic programming, meetinthemiddle 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(n1)$. Then $F$ can be calculated using the following recurrence: $$F(x,k,n) = F(x,k,n1) + F(xf(n1),k1,n)$$ 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(n1) < 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(n1)$. (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(n1)$ is in the sum or not.
Altogether, there are $F(x,k,n1) + F(xf(n1),k1,n)$ ways to form $x$ validly, and we have the recurrence $$F(x,k,n) = F(x,k,n1) + F(xf(n1),k1,n).$$ 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:
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:
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 1This 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:
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:
Using these adjustments, we now have a solution that runs in reasonable time! Solution 2This 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(n1)$ with $k$ summands is $k\cdot f(n1)$, 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!
AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 16 May '16, 00:31

There is also a nonrecursive solution :
Here is my code. answered 16 May '16, 21:01

Can this be solved using the Zeckendorf representation of $X$? Find the Zeckendorf representation greedily, and let its length be $len$. If $len > k$, then $ans = 0$, since you can't "combine" any two numbers in the representation to get a single Fibonacci number. Else, you have to 'break' a Fibonacci number in the representation into smaller parts, such that the number of parts $= k$, and count the number of ways. This is where I got stuck :( answered 16 May '16, 20:03

I solved this by using the property that if a number has to be achieved in k additions then it must have atleast one value greater than or equal to n/k. So i used recursion to assume all values of f greater than n/k are added and the remaining sum is found by having n=nf and k=k1. answered 16 May '16, 15:45

Actually the answer never exceeded ${10}^{9} + 7$. Here is a simple recursive implementation without memoization which works quite fast. Solution Link Basically in recursive solutions, you can either do memoization or cut down the needless length of recursive tree heights. In my solution, I cut down the height of recursive tree height by these 2 simple checks:
For further doubts, you can ask in comment section below :) answered 16 May '16, 16:22

The DP solution was quite obvious. However one thing surprised me the most. Due to large N in the third subtask, I had to use a map for the memoization. It timed out in the last test file of the last subtask. I had to change my approach completely to get AC(using zeckendorf representation). I saw one of my friends solution and he had a similar solution to my DP one but without memoization, it surprisingly passed for full 100 points. I want to ask, why was memoization slow in this case? Is it due to O(logN) insertions in map? answered 16 May '16, 16:47

why is this condition required F(x,k,n)=0 if kf(n−1)<x ? And why is F(0,0,n)=1 ? answered 18 May '16, 11:33

I had never expected solution would't exceed 1e9+7 . Just one condition which reduce the unnecessary recursion enough for AC.
answered 18 May '16, 14:57

is actually the key . Suppose sequence is 1,2,3,5,8,13 ... And you recursively comes at state n = 3 , k = 3 and x = 10 . Now you can form maximum number using k = 3 and n = 3 is f[n1] + f[n1] + f[n1] = 3+3+3 = 9 . But x is 10 . There is no way you can get X = 10 using k=3 and n=3 as you are left with only 1,2 and 3 i.e. f[0] , f[1] and f[2] . Hence no need to do further recursion . answered 18 May '16, 15:10
