HowUnsorted | Topcoder Archive

Problem Statement

The problem statement contains superscripts and subscripts that can be seen in the applet.
Given a randomly generated sequence, it can be useful to know how unsorted it is. The sequence

	a₁, a₂, a₃, a₄, ... , a_n

gets 1 'unsortedness point' for every distinct pair (i,j) where i < j but a_i > a_j. The terms in the sequence are defined by the following formula:

	a₁ = 1   and   a_k = (m * a_k-1 + c) % (2³¹ - 1)

Here % denotes the modulus or remainder operator. Return the number of unsortedness points scored by this n-element sequence.

Definition

Class:: HowUnsorted
Method:: howMany
Parameters:: int, int, int
Returns:: long
Method signature:: long howMany(int m, int c, int n)
(be sure your method is public)

Notes

Make sure to use 64-bit types when generating the random values.

Constraints

m will be between 1 and 2000000000 inclusive.
c will be between 0 and 2^31-2 inclusive.
n will be between 3 and 100000 inclusive.

Examples

```
2
```
```
10
```
```
5
```
```
Returns: 0
```
The sequence used here is: 1, 12, 34, 78, 166 Since the values are sorted, the return is 0.
```
1000
```
```
100
```
```
6
```
```
Returns: 3
```
The sequence here is: 1, 1100, 1100100, 1100100100, 588472836, 62316822 The 3 unsortedness points come from the pairs (4,6), (5,6), and (4,5).
```
1234257123
```
```
123
```
```
1500
```
```
Returns: 558406
```

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.