java - Find a Number of ways to Generate a Number

Question

I have given Fibonacci digits only , i have to find out the numbers of ways to generate a number using K Fibonacci numbers only.

Constraints:

1<=K<=10
1<=N<=10^9

For Example:

N=14 and K=3

There are two ways:

(8,5,1) and (8,3,3) 

Here is my recursive solution:

public static void num_gen(int i ,long val ,int used){

      if(used==0){

          if(val==n) ans++;
          return ;
      }

      if(i==Fib.length) return ;

      for(int j=0;j<=used;j++){

          long x = j*Fib[i];
          if(x+val<=n){
              num_gen(i+1,x+val, used-j);
          }
      }

}

This solution will timeout for large value of N and K=10. Can you provide me algorithm with better complexity.

Answer 1

This can be expressed as multiplying polynomials where exponents are Fibonacci numbers.

Number of factors is K.

The result is a coefficient of the member of the result polynomial whose exponent equals N.

Example: What is the number of ways to compose number 7 from 3 numbers where each of these 3 numbers can be 1,2 or 3.

(x + x2 + x3)3 = x? + 3x? +6x? + 7x? + 6x? + 3x? + x3

Result is 6 since it is the coefficient of the x? member of the result polynomial.