TopCoder Statistics - Problem Statement

Problem Statement

The final round of Top Cat Open 2014 is over! However, we do not know the final standings yet because the scoreboard has been frozen for the last hour.

There are N contestants in the final round. They are numbered 0 through N-1 according to the results of the previous round. According to the frozen standings, contestant i has already solved X[i] problems. After the standings have been frozen, each contestant was only allowed to solve one additional problem. Thus, for each i the actual number of problems solved by contestant i is either X[i] or X[i] + 1.

In the final standings the contestants will be ordered by the number of problems solved (more is better). In case of a tie the contestant with a smaller number will have the better place.

The array X is generated from given ints A and seed. Use the following pseudocode to generate X:

64bit_integer x = seed;
for (i = 0; i &lt; N; i++) {
    x = x * 20142014 % 1000000007;
    X[i] = x % A;
}

How many different rankings are possible at the end of the contest? Return this value modulo 1,000,000,007.

Definition

Class:: FrozenStandings
Method:: countStandings
Parameters:: int, int, int
Returns:: int
Method signature:: int countStandings(int N, int A, int seed)
(be sure your method is public)

Constraints

N will be between 1 and 500,000, inclusive.
A will be between 1 and 500,000, inclusive.
seed will be between 1 and 1,000,000,006, inclusive.

Examples

3

3

2137378

Returns: 2

The array X will be {0, 2, 2}. If contestant 2 solved one more problem during the last hour but contestant 1 did not, the final ranking will be (2,1,0). Otherwise the final ranking will be (1,2,0).
1

1

565225711

Returns: 1

The array X will be {0}.
5

1

765276374

Returns: 27

The array X will be {0, 0, 0, 0, 0}.
8

2

667363653

Returns: 226

The array X will be {1, 0, 1, 1, 1, 0, 1, 1}.
20

4

765276374

Returns: 933806

The array X will be {3, 3, 2, 3, 1, 0, 3, 1, 3, 0, 1, 3, 2, 1, 0, 1, 0, 3, 2, 1}.
500000

100

123456789

Returns: 482934470
500000

1

519250411

Returns: 967131222
500000

1

95631118

Returns: 967131222
500000

1

187586530

Returns: 967131222
500000

1

265376751

Returns: 967131222
500000

1

142232182

Returns: 967131222
500000

2

897576132

Returns: 242696728
500000

2

125068896

Returns: 836583755
500000

2

861796586

Returns: 782868353
500000

2

561547212

Returns: 736429519
500000

2

590315948

Returns: 937264137
500000

3

377145873

Returns: 202610805
500000

3

716199354

Returns: 273839196
500000

3

709244277

Returns: 304940343
500000

3

362451667

Returns: 489754085
500000

3

58954005

Returns: 169646306
500000

4

80617800

Returns: 959125713
500000

5

902358027

Returns: 754652191
500000

6

379290125

Returns: 586468961
500000

7

895850760

Returns: 665740316
500000

8

40537806

Returns: 749502325
500000

9

541593165

Returns: 540954372
500000

10

556476263

Returns: 451757209
500000

16

237982805

Returns: 947120666
500000

32

991900216

Returns: 621878897
500000

64

923939675

Returns: 22285854
500000

128

694457773

Returns: 108497652
500000

256

478760814

Returns: 802202755
500000

512

144385324

Returns: 35627417
500000

1024

629303436

Returns: 83725064
500000

2048

213770903

Returns: 736979896
500000

4096

114471170

Returns: 662581380
500000

8192

717029620

Returns: 343880006
500000

16384

649340539

Returns: 751434004
500000

32768

206734362

Returns: 354296522
500000

65536

405274810

Returns: 515136334
500000

131072

291766580

Returns: 368187458
500000

262144

928763678

Returns: 449979552
500000

500000

741796964

Returns: 501545732
500000

500000

360256101

Returns: 612020017
500000

500000

824345074

Returns: 938585338
500000

500000

526708173

Returns: 213615034
500000

500000

112914283

Returns: 174985997
423458

1

949948944

Returns: 112042571
373828

1

558583823

Returns: 477554873
23211

1

442446780

Returns: 140605250
176338

1

921333394

Returns: 593179935
411953

1

512572382

Returns: 702622078
483535

2

621117970

Returns: 853328917
20147

2

824284065

Returns: 258463483
463147

2

155045233

Returns: 58511148
365249

2

143409881

Returns: 456833239
237930

2

272934246

Returns: 95579415
130359

3

237909481

Returns: 212209150
44118

3

411883325

Returns: 884207573
345933

3

224182395

Returns: 489470039
259999

3

443849912

Returns: 430797982
453674

3

474722482

Returns: 405172840
112107

4

76151679

Returns: 686637123
166829

5

383221681

Returns: 865496167
316922

6

827261919

Returns: 418374461
214761

7

41045349

Returns: 132523877
384054

8

358258325

Returns: 531586250
188868

9

996637423

Returns: 348513858
238266

10

20478855

Returns: 628495728
453877

16

530263928

Returns: 174462135
224609

32

952170923

Returns: 914087210
446572

64

554245691

Returns: 728098977
290596

128

902707522

Returns: 865394167
184429

256

683831022

Returns: 474990298
410557

512

482885036

Returns: 322364490
227446

1024

532332352

Returns: 825586878
369674

2048

321889599

Returns: 458066700
270152

4096

786253257

Returns: 572924033
87382

8192

651715476

Returns: 525351011
83493

16384

545913333

Returns: 159748027
407685

32768

556992282

Returns: 729693210
164047

65536

55859250

Returns: 354843007
471881

131072

451428048

Returns: 912369408
303513

262144

326630576

Returns: 933834910
114874

500000

35109600

Returns: 707415695
109035

500000

438997865

Returns: 761285486
487414

500000

345936604

Returns: 17276329
419250

500000

986395492

Returns: 947416038
171359

500000

300693229

Returns: 823714282

Statistics

Problem Statement for "FrozenStandings"

Problem Statement

Definition

Constraints

Examples