TopCoder problem "HowUnsorted" used in SRM 234 (Division I Level Three)



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 
	a1, a2, a3, a4, ... , an
gets 1 'unsortedness point' for every distinct pair (i,j) where i < j but ai > aj. The terms in the sequence are defined by the following formula: 
	a1 = 1   and   ak = (m * ak-1 + c) % (231 - 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

0)
    
2
10
5
Returns: 0
The sequence used here is: 
	1, 12, 34, 78, 166
Since the values are sorted, the return is 0.
1)
    
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).
2)
    
1234257123
123
1500
Returns: 558406

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3968

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6533&pm=3968

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom

Problem categories:

Sorting