SequenceEvolution | Topcoder Archive

Problem Statement

Basha recently had to endure a long flight between two continents. To keep herself occupied, she generated a very long pseudorandom sequence A and then she modified this sequence by performing a sequence of s steps. Your task is to compute and return a int[] with two elements: the first and the last element of Basha's final sequence.

You are given the long n: the length of Basha's original sequence. You are also given the ints a0, a1, c1, c2, and add: parameters of the pseudorandom generator Basha used. Her initial sequence can be generated by following this pseudocode:

A[0] = a0
A[1] = a1
for i = 2 to n-1:
    A[i] = ( c1*A[i-1] + c2*A[i-2] + add ) modulo (10^9 + 7)

You are also given longs b (block size) and s (number of steps). The modification Basha applied to the sequence in each of the s steps looks as follows:

Remove the first b elements of the sequence (or all elements if the sequence has fewer than b elements already).
Let r be the sum of the removed elements, modulo 10^9 + 7.
Append r to the current sequence.

Definition

Class:: SequenceEvolution
Method:: findEndpoints
Parameters:: long, int, int, int, int, int, long, long
Returns:: int[]
Method signature:: int[] findEndpoints(long n, int a0, int a1, int c1, int c2, int add, long b, long s)
(be sure your method is public)

Constraints

n will be between 2 and 10^18, inclusive.
a0, a1, c1, c2, and add will each be between 0 and 10^9 + 6, inclusive.
b will be between 1 and 10^18, inclusive.
s will be between 0 and 10^18, inclusive.

Examples

```
11
```
```
0
```
```
10
```
```
1
```
```
0
```
```
10
```
```
3
```
```
3
```
```
Returns: {90, 210 }
```
See Example #1 annotation below.
```
11
```
```
0
```
```
10
```
```
1
```
```
0
```
```
10
```
```
3
```
```
4
```
```
Returns: {120, 220 }
```
Both Example 0 and Example 1 define the same sequence A = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100}. In both examples Basha is using block size b = 3. Her first four steps produce the following sequences, in order: {30, 40, 50, 60, 70, 80, 90, 100, 30} {60, 70, 80, 90, 100, 30, 120} {90, 100, 30, 120, 210} {120, 210, 220} Example #0 asked about the sequence after three steps, this example is asking about the sequence after four steps.
```
100
```
```
0
```
```
1
```
```
1
```
```
1
```
```
0
```
```
5
```
```
20
```
```
Returns: {7, 688840473 }
```
Here the sequence A are the first 100 Fibonacci numbers, modulo 1,000,000,007.
```
100
```
```
47
```
```
47
```
```
0
```
```
0
```
```
47
```
```
2
```
```
12345
```
```
Returns: {4700, 4700 }
```
Here the initial sequence A are simply 100 copies of the number 47. Her final sequence is the one-element sequence {4700}. Thus, the first and the last element of her final sequence is the same.

100000000000000047

Returns: {398925423, 398925423 }

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.