FibonacciStringSum | Topcoder Archive

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:

Let x be the number of '0's in s.
Let y be the number of '1's in s.
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

```
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.
```
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.
```
10
```
```
10
```
```
10
```
```
Returns: 518500021
```
Watch out for integer overflow.
```
5000
```
```
20
```
```
20
```
```
Returns: 880245669
```

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.