Connection Status:
Competition Arena > SequenceEvolution

SequenceEvolution

TCO18 Parallel Round 4 · 2018-04-20 · by misof

TCO18 Parallel Round 4 · 2018-04-20 · by misof · Math, Simple Search, Iteration, Simulation
Class Name: SequenceEvolution
Return Type: int[]
Method Name: findEndpoints
Arg Types: (long long, int, int, int, int, int, long long, long long)
Problem Statement

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:

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

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
0)
11
0
10
1
0
10
3
3
Returns: {90, 210 }

See Example #1 annotation below.

1)
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.

2)
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.

3)
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.

4)
47
12
3
456
7
89
100000000000000047
1
Returns: {398925423, 398925423 }

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

Coding Area

Language: C++17 · define a public class SequenceEvolution with a public method vector<int> findEndpoints(long long n, int a0, int a1, int c1, int c2, int add, long long b, long long s) · 135 test cases · 2 s / 256 MB per case

Submitting as anonymous