Statistics

Problem Statement for "FibonacciStringSum"

Problem Statement

A string is called a Fibonacci string if it satisfies the following constraints:
  • Each character of the string is either a '0' or a '1'.
  • There are no two consecutive '1's in the string.
You are given a positive int n. In this problem we will consider Fibonacci strings of length n. You are also given two nonnegative ints a and b. These are used to define the weight of a string. The weight w(s) of a Fibonacci string s is calculated as follows:
  1. Let x be the number of '0's in s.
  2. Let y be the number of '1's in s.
  3. The weight of s is (x^a) * (y^b).
Note that z^0 equals 1 for any z. In particular, when calculating the weight of a string assume that 0^0 = 1. Given n, a and b, find the sum of weights of all Fibonacci strings of length n. Return that sum modulo 10^9 + 7.

Definition

Class:
FibonacciStringSum
Method:
get
Parameters:
int, int, int
Returns:
int
Method signature:
int get(int n, int a, int b)
(be sure your method is public)

Constraints

  • n will be between 1 and 1,000,000,000, inclusive.
  • a will be between 0 and 25, inclusive.
  • b will be between 0 and 25, inclusive.

Examples

  1. 1000000000

    25

    25

    Returns: 572727199

  2. 536870911

    25

    25

    Returns: 449528631

  3. 158260522

    6

    23

    Returns: 640706797

  4. 745344240

    18

    9

    Returns: 894154618

  5. 118642159

    2

    10

    Returns: 36301786

  6. 805214284

    22

    18

    Returns: 179758717

  7. 442238608

    14

    3

    Returns: 764112312

  8. 216618928

    17

    24

    Returns: 802728062

  9. 115516813

    19

    12

    Returns: 903248205

  10. 909788622

    17

    1

    Returns: 711005535

  11. 131071

    5

    17

    Returns: 26802153

  12. 1

    13

    20

    Returns: 0

  13. 131071

    25

    23

    Returns: 956099469

  14. 536870911

    24

    23

    Returns: 916012684

  15. 32767

    21

    24

    Returns: 337339515

  16. 536870911

    18

    24

    Returns: 365331523

  17. 536870911

    21

    25

    Returns: 529664622

  18. 536870911

    21

    19

    Returns: 848699368

  19. 536870911

    20

    25

    Returns: 445715445

  20. 123

    0

    1

    Returns: 52782618

  21. 46543213

    1

    0

    Returns: 219561263

  22. 548792

    0

    0

    Returns: 944243269

  23. 213978

    10

    10

    Returns: 794939670

  24. 321987546

    1

    1

    Returns: 957907653

  25. 268435455

    23

    23

    Returns: 893602578

  26. 536870911

    25

    25

    Returns: 449528631

  27. 268435455

    22

    23

    Returns: 467682482

  28. 3

    0

    0

    Returns: 5

    We have five Fibonacci strings of length 3: "000", "001", "010", "100", "101". As a=b=0, the weight of each Fibonacci string is 1. Hence, the sum of weights of our five strings is 5.

  29. 3

    0

    1

    Returns: 5

    With a=0 and b=1, the weight of a string is the number of ones it contains. The correct return value is w("000") + w("001") + w("010") + w("100") + w("101") = 0 + 1 + 1 + 1 + 2 = 5.

  30. 10

    10

    10

    Returns: 518500021

    Watch out for integer overflow.

  31. 5000

    20

    20

    Returns: 880245669

  32. 1

    0

    0

    Returns: 2

  33. 1

    0

    1

    Returns: 1

  34. 1

    1

    0

    Returns: 1

  35. 1

    1

    1

    Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: