TopCoder Statistics - Problem Statement

Problem Statement

A smooth permutation is a permutation of numbers 1 to N such that the largest element among the first K elements is at most equal to X.

You are given T separate test cases. For each of them, calculate the number of smooth permutations modulo a given M.

You are given the values of N, K and X for a few test cases. Use the pseudocode below to generate the rest of test cases.

A[0] = seed
for i = 1 to 3*T-1:
	A[i] = (A[i-1] * 1103515245 + 12345) modulo 2147483648

LEN = length(prefN)
for i = 0 to LEN-1:
	N[i] = prefN[i]
	K[i] = prefK[i]
	X[i] = prefX[i]
 
for i = LEN to T-1:
	N[i] = (A[i] modulo MX) + 1
	K[i] = (A[T+i] modulo N[i]) + 1
	X[i] = (A[2*T+i] modulo N[i]) + 1

Return the sum of answers across all test cases.

Definition

Class:: SmoothPermutations
Method:: countPermutations
Parameters:: int, int, int, int, int[], int[], int[]
Returns:: long
Method signature:: long countPermutations(int T, int M, int MX, int seed, int[] prefN, int[] prefK, int[] prefX)
(be sure your method is public)

Notes

Be careful with overflows.
The reference solution would correctly solve any case that matches the constraints. It does not depend on the properties of the pseudorandom generator.

Constraints

T will be between 1 and 200,000, inclusive.
M will be between 1 and 1,000,000,000, inclusive.
MX will be between 1 and 200,000, inclusive.
seed will be between 0 and 2,147,483,647, inclusive.
Number of elements in prefN, prefK, prefX will be equal and between 0 and min(500,T), inclusive.
Each element of prefN will be between 1 and MX, inclusive.
For each i, prefK[i] and prefX[i] will be between 1 and prefN[i], inclusive.

Examples

200000

373416572

5

586135019

{}

{}

{}

Returns: 2292074
200000

284159665

28

2104362589

{}

{}

{}

Returns: 10522388292524
200000

603641977

13

1868932308

{}

{}

{}

Returns: 3598451238526
200000

761781896

51

1007685845

{}

{}

{}

Returns: 32130912337239
200000

867928711

71

1340110876

{}

{}

{}

Returns: 39331323581484
200000

33644295

7

879741206

{}

{}

{}

Returns: 49071011
200000

190821497

8

1307088232

{}

{}

{}

Returns: 1052073714
200000

28034316

13

68994150

{}

{}

{}

Returns: 280755162623
200000

386533129

42

1420760476

{}

{}

{}

Returns: 16387486131062
200000

943000708

57

1325036361

{}

{}

{}

Returns: 41176897745236
200000

199084508

56

631313631

{}

{}

{}

Returns: 8894665825892
200000

867542476

33

1424847237

{}

{}

{}

Returns: 32633747275018
200000

467544099

40

1483670165

{}

{}

{}

Returns: 19326139576495
200000

806975643

54

226285086

{}

{}

{}

Returns: 33942454744939
200000

880893328

28

730329443

{}

{}

{}

Returns: 30669413735573
200000

215808020

48

778535769

{}

{}

{}

Returns: 9626860670210
200000

334820498

16

705226541

{}

{}

{}

Returns: 6544379610902
200000

54199046

52

1110275772

{}

{}

{}

Returns: 2433531441573
200000

841358463

84

1814048026

{}

{}

{}

Returns: 40974970552056
200000

83914069

36

864885004

{}

{}

{}

Returns: 3573155879530
200000

437847091

451

1994694541

{}

{}

{}

Returns: 21918111848204
200000

753310108

469

1928629837

{}

{}

{}

Returns: 37702474326341
200000

595360603

385

10550829

{}

{}

{}

Returns: 29766160922895
200000

815400598

751

451347908

{}

{}

{}

Returns: 40917522654154
200000

726758003

547

512965597

{}

{}

{}

Returns: 36401765620803
200000

479843612

780

945162743

{}

{}

{}

Returns: 24142809876558
200000

775246000

462

555732676

{}

{}

{}

Returns: 38942641003593
200000

962906626

649

468635818

{}

{}

{}

Returns: 48286293883730
200000

436141501

95

595132485

{}

{}

{}

Returns: 21133246307799
200000

494598600

794

1499171555

{}

{}

{}

Returns: 24840411748603
200000

188985185

715

330972422

{}

{}

{}

Returns: 9431072015495
200000

413577153

572

1501082854

{}

{}

{}

Returns: 20742644422847
200000

626065941

608

947348716

{}

{}

{}

Returns: 31551584874789
200000

505799289

437

612263480

{}

{}

{}

Returns: 25177476801126
200000

383830279

561

2025855773

{}

{}

{}

Returns: 19263115108421
200000

596835941

946

1226678687

{}

{}

{}

Returns: 29887287541564
200000

496381453

524

1805063676

{}

{}

{}

Returns: 25069510851790
200000

788451736

407

93431072

{}

{}

{}

Returns: 39371223515868
200000

563863220

175

1943891759

{}

{}

{}

Returns: 27709241936806
200000

178960918

482

396704255

{}

{}

{}

Returns: 8929470332321
200000

745031640

22

1840378779

{}

{}

{}

Returns: 16951125586305
200000

10211402

880

1487668417

{}

{}

{}

Returns: 513388841798
200000

506903144

133

843346789

{}

{}

{}

Returns: 25150479333391
200000

497852268

45

175101228

{}

{}

{}

Returns: 20666397348315
200000

648725824

755

1998393842

{}

{}

{}

Returns: 32623558341699
200000

858785178

335

2047997508

{}

{}

{}

Returns: 42831906085395
200000

896271431

620

1305974247

{}

{}

{}

Returns: 45222558796568
200000

79141750

482

1574993487

{}

{}

{}

Returns: 3949596657283
200000

665609471

493

1230158121

{}

{}

{}

Returns: 33290939700260
200000

749759464

420

320839377

{}

{}

{}

Returns: 37499001030768
200000

785724832

107

223574236

{}

{}

{}

Returns: 37628525488161
200000

11287110

393

549909648

{}

{}

{}

Returns: 566164684906
200000

43907464

875

1302095207

{}

{}

{}

Returns: 2204709091593
200000

160264289

663

607311760

{}

{}

{}

Returns: 8032357880107
200000

340682616

626

24703598

{}

{}

{}

Returns: 17138903701337
200000

218500845

451

214543127

{}

{}

{}

Returns: 11009742247027
200000

756158736

613

1354548950

{}

{}

{}

Returns: 37891666877238
200000

403805504

465

1268067753

{}

{}

{}

Returns: 20228763266665
200000

811301166

689

2134314179

{}

{}

{}

Returns: 40593418684294
200000

826622857

430

1540344075

{}

{}

{}

Returns: 41404880591387
200000

280634623

150531

1536803228

{}

{}

{}

Returns: 13983767202165
200000

655080126

130850

1231413827

{}

{}

{}

Returns: 32650395872145
200000

989307806

22317

1993672196

{}

{}

{}

Returns: 49475221794541
200000

914544549

35312

443230614

{}

{}

{}

Returns: 45626967140475
200000

766864911

104322

686190050

{}

{}

{}

Returns: 38279539247388
200000

572400895

132307

1082387080

{}

{}

{}

Returns: 28670579732488
200000

855025158

108913

672944217

{}

{}

{}

Returns: 42777628491774
200000

700208440

48929

2000837598

{}

{}

{}

Returns: 35006936691323
200000

921815608

60034

936187856

{}

{}

{}

Returns: 46231306045354
200000

275189599

197306

880275358

{}

{}

{}

Returns: 13797589536232
200000

242049161

132863

864195050

{}

{}

{}

Returns: 12100111169765
200000

53774913

170453

259695372

{}

{}

{}

Returns: 2708185250364
200000

286027462

60562

2073640845

{}

{}

{}

Returns: 14284430615071
200000

953628815

58568

1147031213

{}

{}

{}

Returns: 47782480189362
200000

825643499

137052

139699423

{}

{}

{}

Returns: 41441019077037
200000

635281170

55810

941749832

{}

{}

{}

Returns: 31712479353189
200000

223282586

81197

677484867

{}

{}

{}

Returns: 11198880801988
200000

755525176

152083

584128735

{}

{}

{}

Returns: 37734154186506
200000

13668338

93674

802920287

{}

{}

{}

Returns: 683078243700
200000

304932067

175961

1150877881

{}

{}

{}

Returns: 15182199025707
200000

610546839

66590

481430808

{}

{}

{}

Returns: 30534703356002
200000

767247760

167247

1255281499

{}

{}

{}

Returns: 38553277969201
200000

779585491

179485

1972415379

{}

{}

{}

Returns: 39082409489051
200000

38445942

34177

1241325960

{}

{}

{}

Returns: 1927354172806
200000

660711416

84651

1748350773

{}

{}

{}

Returns: 33015128476842
200000

395186363

64237

1907668808

{}

{}

{}

Returns: 19874372573796
200000

805631340

49607

1815959459

{}

{}

{}

Returns: 40216811995678
200000

375336460

84562

1603431390

{}

{}

{}

Returns: 18709676273737
200000

793389958

62785

1868621762

{}

{}

{}

Returns: 39497226669457
200000

231242343

154575

906506703

{}

{}

{}

Returns: 11527790175882
200000

519166522

170805

1344947639

{}

{}

{}

Returns: 25880827831776
200000

741897790

54772

1546495713

{}

{}

{}

Returns: 37179872865354
200000

548304081

131758

739975911

{}

{}

{}

Returns: 27328821645446
200000

823319890

40454

193029144

{}

{}

{}

Returns: 41360402274493
200000

94459670

104924

1179145207

{}

{}

{}

Returns: 4706914434373
200000

323678110

26249

278810042

{}

{}

{}

Returns: 16240759817408
200000

591898567

187482

191439051

{}

{}

{}

Returns: 29673406948932
200000

283560328

193925

1675944779

{}

{}

{}

Returns: 14198191456280
200000

634244666

120335

2019202186

{}

{}

{}

Returns: 31650244504149
200000

582172011

39197

2132316048

{}

{}

{}

Returns: 29117966748739
200000

312841624

90878

1746324888

{}

{}

{}

Returns: 15634465284129
200000

796095921

137255

351336591

{}

{}

{}

Returns: 39661959917722
200000

998216830

196254

236998041

{}

{}

{}

Returns: 49918554226549
200000

223531503

40766

262098829

{}

{}

{}

Returns: 11172017148539
200000

382666809

154094

576801140

{}

{}

{}

Returns: 19130727544407
200000

739966712

96846

2068291853

{}

{}

{}

Returns: 37050812192070
200000

773478300

142444

58653004

{}

{}

{}

Returns: 38522508666154
200000

941826794

54772

1097737431

{}

{}

{}

Returns: 47041321550383
200000

509304235

109187

1419831432

{}

{}

{}

Returns: 25617487640172
200000

514620659

49040

1515752942

{}

{}

{}

Returns: 25662211874747
200000

121409430

168983

1538016715

{}

{}

{}

Returns: 6080763325183
200000

791107305

35205

1499683479

{}

{}

{}

Returns: 39637565027451
200000

308976964

107677

619918076

{}

{}

{}

Returns: 15471967202825
200000

783915675

190341

2034967640

{}

{}

{}

Returns: 39102974480219
200000

890090187

153875

827856190

{}

{}

{}

Returns: 44399459105889
200000

837251096

132989

225046517

{}

{}

{}

Returns: 41784128779463
200000

516198820

32687

870638839

{}

{}

{}

Returns: 25806876971901
200000

448505548

113385

2095611251

{}

{}

{}

Returns: 22443763901587
200000

602313742

117282

601259468

{}

{}

{}

Returns: 30120908911777
200000

421859543

40217

753113113

{}

{}

{}

Returns: 21105926143411
200000

289287854

67680

672919203

{}

{}

{}

Returns: 14503171064577
200000

290820631

109283

2122671721

{}

{}

{}

Returns: 14521606350981
200000

821717309

139708

558483871

{}

{}

{}

Returns: 41031908528905
200000

875624223

154721

1175632426

{}

{}

{}

Returns: 43929603865757
200000

537287298

170752

1459713062

{}

{}

{}

Returns: 26891488068677
200000

312565067

81588

1609326688

{}

{}

{}

Returns: 15566438266172
200000

435988790

97064

231503581

{}

{}

{}

Returns: 21847386541646
200000

948239904

65015

1216639313

{}

{}

{}

Returns: 47611230795074
200000

99942995

114563

174837161

{}

{}

{}

Returns: 5014449007697
200000

807032250

180090

1548198018

{}

{}

{}

Returns: 40256821397791
200000

336984917

194442

1201354671

{}

{}

{}

Returns: 16968652271074
200000

352574174

175141

612011190

{}

{}

{}

Returns: 17633467522491
200000

930537722

48951

1665697620

{}

{}

{}

Returns: 46331036466416
200000

132087832

196889

1443565557

{}

{}

{}

Returns: 6628638927976
200000

415745662

34733

138342972

{}

{}

{}

Returns: 20787657383679
200000

993878582

123933

1733660545

{}

{}

{}

Returns: 49773387595010
200000

716364636

142555

1497784654

{}

{}

{}

Returns: 35684307227809
200000

960394403

198549

1641958370

{}

{}

{}

Returns: 47860222660171
200000

579923850

31587

582402222

{}

{}

{}

Returns: 29063219202636
200000

583766332

61651

1425977562

{}

{}

{}

Returns: 29308972199812
200000

637505237

63336

1467961281

{}

{}

{}

Returns: 31810218054732
200000

479675942

186196

243705200

{}

{}

{}

Returns: 23984929189786
200000

941970250

124961

513929515

{}

{}

{}

Returns: 46912692233115
200000

249264656

54652

2119293929

{}

{}

{}

Returns: 12403153201240
200000

507569501

112315

1981971155

{}

{}

{}

Returns: 25329566802502
200000

949124472

176392

1775313353

{}

{}

{}

Returns: 47440365393343
200000

348550873

33007

812254685

{}

{}

{}

Returns: 17421748013580
200000

457624176

37920

1418178517

{}

{}

{}

Returns: 22875607924956
200000

640180043

80812

1360936621

{}

{}

{}

Returns: 31846937190915
200000

254655737

102667

1115453971

{}

{}

{}

Returns: 12749710741553
200000

121272446

33688

242005226

{}

{}

{}

Returns: 6066536365471
200000

738757269

158109

966754247

{}

{}

{}

Returns: 36817864095249
200000

474932158

67074

2076846967

{}

{}

{}

Returns: 23833019489409
200000

247401201

158772

656612215

{}

{}

{}

Returns: 12463300079361
200000

434828815

102616

589686906

{}

{}

{}

Returns: 21611237508024
200000

439621046

191873

231297767

{}

{}

{}

Returns: 22014794496001
200000

632638372

83927

294716761

{}

{}

{}

Returns: 31620068498841
200000

210228466

77032

572860189

{}

{}

{}

Returns: 10512468563540
200000

998125730

121803

475643575

{}

{}

{}

Returns: 50009361259749
200000

978356825

68303

969925725

{}

{}

{}

Returns: 48905025908042
200000

168422941

118742

1671087226

{}

{}

{}

Returns: 8442135459519
200000

4316964

66224

848458285

{}

{}

{}

Returns: 215775457604
200000

297158179

113256

1463716295

{}

{}

{}

Returns: 14859386804203
200000

217948070

111113

914531153

{}

{}

{}

Returns: 10976342727758
200000

380165765

38687

1131844868

{}

{}

{}

Returns: 19001002734483
200000

214366184

182358

34899406

{}

{}

{}

Returns: 10711858339431
200000

927306480

58089

698798036

{}

{}

{}

Returns: 46262871818562
200000

57321058

71439

287290090

{}

{}

{}

Returns: 2864169202287
200000

524717480

124707

1791285021

{}

{}

{}

Returns: 26323221131175
200000

273014772

90084

1473814314

{}

{}

{}

Returns: 13574604926567
200000

271947817

161982

137054980

{}

{}

{}

Returns: 13601908776080
200000

164360704

52856

1824385618

{}

{}

{}

Returns: 8279807135778
200000

650126126

102778

2145459950

{}

{}

{}

Returns: 32550367906542
200000

832182452

30572

1215934311

{}

{}

{}

Returns: 41666224398553
200000

58780376

85315

156559744

{}

{}

{}

Returns: 2933720402474
200000

228631641

173164

11981999

{}

{}

{}

Returns: 11442311283763
200000

293262935

107277

931935390

{}

{}

{}

Returns: 14636032104956
200000

767967463

117638

585784238

{}

{}

{}

Returns: 38526970436653
200000

130928367

111153

1170656623

{}

{}

{}

Returns: 6531880376981
200000

200873007

29507

336638249

{}

{}

{}

Returns: 10020272911990
200000

273740345

80968

328602711

{}

{}

{}

Returns: 13697975847827
200000

864692726

72557

442432807

{}

{}

{}

Returns: 43105144706988
200000

931177357

185030

359156987

{}

{}

{}

Returns: 46522979193586
200000

695772832

173609

1978168042

{}

{}

{}

Returns: 34833458042471
200000

107541209

113097

1049095743

{}

{}

{}

Returns: 5410017367839
200000

94094639

157840

758620409

{}

{}

{}

Returns: 4694644613517
200000

175924192

94222

697233994

{}

{}

{}

Returns: 8797150445192
200000

226682862

116594

1927004441

{}

{}

{}

Returns: 11349010248650
200000

445634171

59438

72230528

{}

{}

{}

Returns: 22316896701994
200000

729425965

195228

1223297102

{}

{}

{}

Returns: 36461930102728
200000

193755338

117186

69761925

{}

{}

{}

Returns: 9717919509642
200000

65461652

126633

1198716637

{}

{}

{}

Returns: 3288389667653
200000

101046805

29720

1742886208

{}

{}

{}

Returns: 5030372366586
200000

546503018

87281

720087116

{}

{}

{}

Returns: 27430613403362
200000

148362902

153035

1273289428

{}

{}

{}

Returns: 7423152652325
200000

666992876

111885

260776799

{}

{}

{}

Returns: 33428016222915
200000

910382691

149026

1442137768

{}

{}

{}

Returns: 45543849101957
200000

119994451

146762

2124130844

{}

{}

{}

Returns: 5988185649157
200000

72061402

171403

2103457375

{}

{}

{}

Returns: 3608676573781
200000

519952783

129373

851446215

{}

{}

{}

Returns: 25991841692285
3

100

5

4

{5,4}

{3,2}

{5,2}

Returns: 24

The generated arrays will be: N = {5,4,4} K = {3,2,2} X = {5,2,1} Thus, we have the following test cases: permutations of 1..5 in which the largest among the first 3 elements is at most 5 permutations of 1..4 in which the largest among the first 2 elements is at most 2 permutations of 1..4 in which the largest among the first 2 elements is at most 1 The answers for these are as follows: In the first test case, all 5! permutations are smooth permutations, and 5! mod 100 = 120 mod 100 = 20. In the second test case, the following 4 permutations are smooth permutations: (1,2,3,4), (2,1,3,4), (1,2,4,3), and (2,1,4,3). In the third test case there are no smooth permutations. Hence, the correct return value is 20 + 4 + 0 = 24.
10

64

34

21

{5,8,13,2}

{4,1,5,1}

{3,2,10,1}

Returns: 49
25

534

342

12

{10,2,8,6,5}

{4,2,4,4,4}

{10,2,3,2,3}

Returns: 872
100

1

47

47

{}

{}

{}

Returns: 0

Anything modulo 1 is 0.
100

999999937

123456

47

{}

{}

{}

Returns: 24359438587

Note that the correct return value is just a plain sum of all test case answers. (It should not be taken modulo M.)
200000

2

200000

139391

{}

{}

{}

Returns: 0
200000

3

200000

131931

{}

{}

{}

Returns: 3
200000

999999999

200000

47

{ }

{ }

{ }

Returns: 50247057235422
200000

200000

200000

200000

{ }

{ }

{ }

Returns: 879526
200000

1000000000

200000

200000

{ }

{ }

{ }

Returns: 6620479526
200000

1000

200000

1

{ }

{ }

{ }

Returns: 4511
200000

999999999

200000

123

{ }

{ }

{ }

Returns: 50165420690292
200000

40320

200000

35235

{ }

{ }

{ }

Returns: 30254
200000

223092870

200000

1

{ }

{ }

{ }

Returns: 657688111
200000

99999966

200000

47

{ }

{ }

{ }

Returns: 22073556474
200000

1000000000

200000

666666

{ }

{ }

{ }

Returns: 8138426188
200000

999999937

199888

47

{ }

{ }

{ }

Returns: 50359923145510
200000

120

120

456

{12 }

{5 }

{6 }

Returns: 111198
200000

999999937

123456

47

{ }

{ }

{ }

Returns: 50192684520263
2

7

5

4

{3, 3 }

{3, 3 }

{3, 3 }

Returns: 12
2

28

51

48

{7, 39 }

{1, 32 }

{3, 11 }

Returns: 4

Statistics

Problem Statement for "SmoothPermutations"

Problem Statement

Definition

Notes

Constraints

Examples