1009. K-based Numbers

Let’s consider K-based numbers, containing exactly N digits. We define a number to be valid if its K-based notation doesn’t contain two successive zeros. For example: 

1010230 is a valid 7-digit number;
1000198 is not a valid number;
0001235 is not a 7-digit number, it is a 4-digit number. 

Given two numbers N and K, you are to calculate an amount of valid K based numbers, containing N digits.
You may assume that 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18.

Input
The numbers N and K in decimal notation separated by the line break.

Output
The result in decimal notation.

Sample
Input
2
10


Output
90

http://acm.timus.ru/problem.aspx?space=1&num=1009

Solucion:

* Caso k = 2, y se permiten ceros al inicio:

Definimos F( n ) como la cantidad de numeros binarios de n digitos
tal que ninguno de esos numeros contenga 2 ceros consecutivos.

    Por ejemplo F( 3 ) = 5 { 010, 011, 101, 110, 111 }

    Podemos definir F de manera recursiva:

    * Cuando n = 1, F( 1 ) = 2
    * Cuando n = 2, F( 2 ) = 3

    * Cuando n >= 3, Existen dos posibilidades:

        * Caso 1: El primer digito es 1, y los siguientes n-1 digitos               
          forman un numero binario sin 2 ceros consecuitvos: F( n - 1 )

        * Caso 2: El primer digito es 0, el segundo es 1, y los                     
          siguientes n-2 digitos forman un numero binario sin 2 ceros 

          consecutivos: F( n - 2 )

    Por tanto F( n ) = F( n - 1 ) + F( n - 2 )

* Caso k arbitrario, y se permiten ceros al inicio:

Aplicando un analisis similar al anterior, definimos F( n, k ) como la cantidad
de numeros en base k de n digitos tal que ninguno de esos numeros contenga 2
ceros consecutivos.

   * Cuando n = 1, F( 1, k ) = k
   * Cuando n = 2, F( 2, k ) = k * k - 1

   * Cuando n >= 3, 
         F( n, k ) = ( k-1 ) * F( n-1, k ) + ( k-1 ) * F( n-2, k )

* Caso k arbitrario, sin ceros al inicio ( lo que pide el problema ): 

Esta cantidad que estamos buscando es igual a todos los numeros
cuyo primer digito es 1 o 2 o 3 o ... o 9, y cuyos n-1 siguientes
digitos sean numeros en base k que no contengan ceros consecutivos.

      Cant. Numeros validos = ( k - 1 ) * F( n - 1 )

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Problema1009 
{
   public static void main( String[] args ) throws Exception
   {
      BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
  
      int N = Integer.parseInt( br.readLine() );
      int K = Integer.parseInt( br.readLine() );
  
      int numPosibles = ( K - 1 ) * F( N - 1, K );
  
      System.out.println( numPosibles );
   }
 
   public static int F( int N, int K )
   {
      // Casos Bases
      if( N == 1 )
         return K;
  
      if( N == 2 )
         return K * K - 1;
  
      // Calculamos previamente los casos iniciales
      int ant = K;
      int act = K * K - 1;
      int temp;
  
      /*
      * Partimos de los casos mas pequeños hasta llegar
      * al caso mas grande N.
      */
      for( int i = 3; i <= N; i ++ )
      {
         temp = ( K - 1 ) * ( ant + act );
         ant = act;
         act = temp;
      }
  
      return act;
   }
}