FibonacciStringSum

SRM 701 · 2016-10-02 · by Arterm

SRM 701 · 2016-10-02 · by Arterm · Advanced Math, Dynamic Programming

Show categories

Class Name: FibonacciStringSum

Return Type: int

Method Name: get

Arg Types: (int, int, int)

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.

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.

Statement by TopCoder, Inc. — view the original on the archive.

Examples

1000000000
25
25
Returns: 572727199

536870911
25
25
Returns: 449528631

158260522
6
23
Returns: 640706797

745344240
18
9
Returns: 894154618

118642159
2
10
Returns: 36301786

27)

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.

28)

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.

29)

10
10
10
Returns: 518500021

Watch out for integer overflow.

Submissions are judged against all 35 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FibonacciStringSum with a public method int get(int n, int a, int b) · 35 test cases · 2 s / 256 MB per case