TopCoder problem "TheLuckySequence" used in SRM 403 (Division I Level Two)



Problem Statement

    

John thinks 4 and 7 are lucky digits, and all other digits are not lucky. A lucky number is a number that contains only lucky digits in decimal notation.

A lucky sequence is a sequence of length numbers A[0], A[1], ..., A[length - 1] that satisfies all of the following properties:

  • Each number A[i] is lucky, where 0 <= i < length.
  • For each i, where 0 <= i < length, there exists at least one j such that A[i] = numbers[j].
  • For each i, where 0 <= i < length - 1, the last digit of A[i] is the same as the first digit of A[i + 1].

You are given a int[] numbers and an int length. Return the number of distinct lucky sequences modulo 1234567891.

 

Definition

    
Class:TheLuckySequence
Method:count
Parameters:int[], int
Returns:int
Method signature:int count(int[] numbers, int length)
(be sure your method is public)
    
 

Notes

-Two lucky sequences A[0], A[1], ..., A[length - 1] and B[0], B[1], ..., B[length - 1] are considered distinct if there exists i, 0 <= i < length, such that A[i] ≠ B[i].
 

Constraints

-numbers will contain between 1 and 50 elements, inclusive.
-Each element of numbers will be between 1 and 1,000,000,000, inclusive.
-length will be between 1 and 1,000,000,000, inclusive.
 

Examples

0)
    
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
1
Returns: 2
There are only two lucky numbers among these ten integers.
1)
    
{47, 74, 47}
3
Returns: 2
We can construct only two different sequences (47, 74, 47) and (74, 47, 74).
2)
    
{100, 4774, 200, 747, 300}
47
Returns: 2
3)
    
{44, 47, 74, 77}
2
Returns: 8

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8569

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12175&pm=8569

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Recursion