TopCoder Statistics - Problem Statement

Problem Statement

You are given ints N, X0, XMul, XAdd, XMod, Y0, YMul, YAdd, YMod. Generate N+2 points (X[0], Y[0]), (X[1], Y[1]), ..., (X[N+1], Y[N+1]) as follows:

X[0] = X0,
X[i] = (X[i-1] * XMul + XAdd) % XMod, 0 &lt; i &lt; N+2,
Y[0] = Y0,
Y[i] = (Y[i-1] * YMul + YAdd) % YMod, 0 &lt; i &lt; N+2.

You can assume that no two of those N+2 points will coincide and no 3 points will lie on the same straight line.

Let S be the set of points 0-th to (N-1)-th, P be the N-th point and Q be the (N+1)-th point. In other words, S = {(X[0], Y[0]), (X[1], Y[1]), ..., (X[N-1], Y[N-1])}, P = (X[N], Y[N]) and Q = (X[N+1], Y[N+1]). A subset T of points from S is called nice if:

It contains at least 3 points.
The convex hull of points from T contains both P and Q inside itself. (See notes for the definition of "convex hull".)

Return the number of nice subsets, modulo 1,000,000,007.

Definition

Class:: PQHulls
Method:: countSubsets
Parameters:: int, int, int, int, int, int, int, int, int
Returns:: int
Method signature:: int countSubsets(int N, int X0, int XMul, int XAdd, int XMod, int Y0, int YMul, int YAdd, int YMod)
(be sure your method is public)

Notes

A set of points A is called convex if for any two points p1 and p2 from A, all points of the line segment p1-p2 also belong to A.
A polygon is called convex if its interior is a convex set.
A set S is called minimal with respect to a certain property, if this property is true for S, but false for any proper subset of S.
The convex hull of a set of points A is the minimal convex set that contains all points from A. The convex hull can be shown to be a convex polygon with all vertices being points from A.

Constraints

N will be between 3 and 2,000, inclusive.
XMod and YMod will each be between 1 and 100,000,000, inclusive.
X0, XMul and XAdd will each be between 0 and XMod-1, inclusive.
Y0, YMul and YAdd will each be between 0 and YMod-1, inclusive.
No two of the N+2 points (generated as described in the problem statement) will occupy the exact same place.
No three of the N+2 points (generated as described in the problem statement) will lie on the same straight line.

Examples

4

3

3

3

10

0

3

2

7

Returns: 3

S = {(3, 0), (2, 2), (9, 1), (0, 5)}. P = (3, 3). Q = (2, 4). A nice subset needs to contain points 2 and 3 and least one of points 0 and 1.
5

1

5

6

8

5

5

3

9

Returns: 5

S = {(1, 5), (3, 1), (5, 8), (7, 7), (1, 2)}. P = (3, 4). Q = (5, 5). 4 nice subsets can be obtained by taking points 0, 1 and 3, and by optionally adding each of the points 2 and 4 to them. One more nice subset consists of points 1, 2, 3 and 4.
5

4

1

1

8

5

4

4

6

Returns: 0

There can be no nice subsets.
99

9461448

38301228

33476602

42996440

10502745

35649230

12271470

65500929

Returns: 181248946
1000

11771634

21704604

13316454

26118772

53463288

55273813

30780036

63626191

Returns: 997658387
2000

6927240

2020343

10323527

10690663

28749177

29744699

60134478

78767213

Returns: 143010383
7

3

15

3

19

18

17

10

19

Returns: 16
7

15

3

15

16

16

6

16

17

Returns: 0
3

19

17

2

20

6

3

0

7

Returns: 0
10

13

5

13

19

6

1

4

7

Returns: 128
8

1

1

19

20

18

15

11

19

Returns: 72
9

11

2

7

13

19

1

7

20

Returns: 62
3

10

2

18

20

12

1

6

20

Returns: 0
10

11

1

17

20

17

5

17

19

Returns: 0
6

6

5

5

8

5

5

6

7

Returns: 0
3

4

1

5

6

19

12

12

20

Returns: 0
4

13

2

0

14

16

5

13

17

Returns: 1
3

3

1

7

8

16

12

0

17

Returns: 0
8

0

5

10

11

10

13

10

16

Returns: 55
10

4

17

0

19

18

11

19

20

Returns: 0
5

7

1

8

20

10

10

13

15

Returns: 0
4

10

7

10

11

17

17

2

19

Returns: 0
4

16

6

12

17

10

3

3

11

Returns: 0
5

12

17

13

19

12

5

11

13

Returns: 0
9

18

13

18

19

4

1

4

17

Returns: 168
3

0

2

15

16

17

6

17

20

Returns: 0
4

6

1

17

19

5

11

11

14

Returns: 0
3

3

5

13

14

2

3

4

5

Returns: 0
9

0

3

3

19

5

5

0

19

Returns: 0
4

10

2

0

19

10

9

10

11

Returns: 0
7

0

12

14

15

0

16

3

19

Returns: 0
10

2

12

13

19

16

7

17

18

Returns: 579
5

13

2

14

20

1

14

16

17

Returns: 4
4

10

6

0

19

5

4

3

19

Returns: 0
9

13

3

1

17

13

9

14

17

Returns: 162
6

3

3

12

17

0

17

18

20

Returns: 18
4

1

7

8

15

0

18

19

20

Returns: 2
4

0

8

4

14

0

2

17

18

Returns: 0
3

19

11

13

20

1

1

5

6

Returns: 0
4

1

13

7

17

1

1

3

11

Returns: 0
3

0

16

18

20

0

1

4

14

Returns: 0
6

13

4

4

18

19

18

18

20

Returns: 0
7

14

13

11

15

2

5

9

16

Returns: 0
4

0

2

3

20

5

11

17

20

Returns: 0
4

7

2

19

20

9

1

9

10

Returns: 0
3

9

18

16

20

19

13

7

20

Returns: 0
3

0

1

3

20

18

13

18

19

Returns: 0
3

0

12

13

15

15

6

5

19

Returns: 0
3

1

1

2

3

0

6

5

8

Returns: 0
4

16

10

0

17

13

13

12

15

Returns: 0
3

14

3

6

19

16

16

13

20

Returns: 0
6

18

17

16

20

12

2

6

13

Returns: 12
3

0

16

17

18

0

6

2

20

Returns: 0
3

0

9

12

13

2

1

3

4

Returns: 0
10

18

5

15

19

16

2

0

17

Returns: 713
4

2

1

5

9

4

13

16

17

Returns: 0
8

949

97611326

99068033

99171347

440001

99999706

93983379

100000000

Returns: 93
10

5930

219648

219449

219652

78366462

78369644

915723

78369664

Returns: 0
5

710525

53

93

99999997

30850

30848

3119

30852

Returns: 7
10

6

83

37

118

895

22363346

0

22364759

Returns: 336
10

1486

5

1479

1487

98093739

125

98090940

98093741

Returns: 0
7

270

403

386

413

224787

760907

99889942

99890633

Returns: 34
7

247

16296

5709

22361

68

6

11

71

Returns: 47
4

6

1

3167

6951

0

24287

25188

54766

Returns: 0
7

0

6

447

449

6092

3

6078

6093

Returns: 21
3

32

6

53022

406852

345037

35

341297

345066

Returns: 0
6

8309639

96432502

99999253

99999969

35

535514

98012127

98016164

Returns: 15
9

1469

7350931

13871

99885834

64329

34814774

6631908

92190915

Returns: 0
10

99984321

218

99994325

99998389

88998079

98496868

99847312

99965569

Returns: 599
8

871972

119761

856583

872039

3392

99999864

201959

99999873

Returns: 104
7

3326

23187980

99999862

99999864

1867

99743579

2834765

99743609

Returns: 0
8

55102488

91715648

99989050

99989052

99999472

99964078

99723239

99999525

Returns: 0
9

857806

12236793

74287805

74385226

1

84

1997

417860

Returns: 144
8

0

9

84

257

37922

35264

6

38024

Returns: 31
9

587120

43

2149

587121

298

99945073

342465

99999056

Returns: 94
6

3114

181

16166

110125

99999995

99780822

7528

99999996

Returns: 14
4

61170

21839325

1

21889447

20955

41163835

96715879

96715883

Returns: 3
10

1

8

248178

248192

57

661846

633378

661904

Returns: 615
10

9536

99999994

6041462

100000000

68706078

96

99986135

100000000

Returns: 184
7

99837496

99220658

99837464

99837498

38

83

10

85

Returns: 28
5

27444352

8722868

96109090

96630178

14181528

13898762

8327207

14181529

Returns: 5
7

0

2

236

373

1062766

128796

0

100000000

Returns: 28
4

235597

99998490

99998441

99998493

952593

1

74795869

74796165

Returns: 0
4

6515427

6514108

1921

6515482

2

1

2

8

Returns: 1
3

15178

18706568

22399

18706605

75637443

15

99998566

99998574

Returns: 0
10

6148820

99998213

418

99999994

140444

265734

23

327959

Returns: 0
3

2256750

822660

1

2285008

98021091

97995608

1108923

98021779

Returns: 0
3

0

2365

60

9534

68022263

476271

98310502

99999981

Returns: 0
8

130

3630

54

6422

104867

43242380

56908377

56917202

Returns: 32
8

99999097

99999996

8034

99999999

88

268972

1

269054

Returns: 48
10

7293

143002

143116

143298

9

192493

99766694

99999102

Returns: 212
7

9

4784914

4771816

4785456

1062839

1067437

1018895

1069548

Returns: 0
9

56

56

56

59

99999944

99999971

99996533

99999975

Returns: 185
7

32

7

15

33

4086075

3501

0

4086159

Returns: 8
4

37337

2131301

21525027

21525028

589

92643835

92642297

92643912

Returns: 3
3

7805701

99933522

99605574

99999999

63

892

2282

3421

Returns: 0
3

7

251

2

100000000

0

7139383

4402050

7140406

Returns: 0
4

37301486

37301481

0

37301487

219

279

2

39139355

Returns: 0
6

910

77424119

5472

99957146

0

71170597

70905305

71170825

Returns: 8
6

16034

63107934

760

99998165

44

429

66

99999798

Returns: 18
3

12857039

12948877

175560

12953643

33

1781239

12

1781281

Returns: 1
3

17039

71503

24858

71505

297

281

277

298

Returns: 0
10

380

696752

91994436

99999995

99999174

53439764

32253

99999978

Returns: 0
9

99880721

4851

99997032

99997047

5365

79889204

99973045

99999997

Returns: 0
6

99638548

92277665

12293246

99638740

99996183

99880835

566965

99996188

Returns: 12
10

99999722

99954125

4650794

99999965

99995846

14515

99999635

99999639

Returns: 640
15

22006

82289

82303

82304

1411210

99691612

99982420

99983252

Returns: 19793
40

99893948

27237738

99893942

99893950

13881

13528

14639

14641

Returns: 471513882
98

99770944

1896

99050856

99999999

35

93545687

98997876

99835628

Returns: 440262276
4

68492027

91256627

91255714

91257266

5021802

2951676

0

99999994

Returns: 0
33

230

34016888

99542552

99936340

99890324

78299310

4819810

99890325

Returns: 147480946
98

13099

99997482

67086622

100000000

53134934

16746589

77261820

95305101

Returns: 741192573
68

99990999

35728404

18760895

99999983

45004353

54630035

54629501

54631020

Returns: 901847712
7

99986993

12880

5

99987083

3462019

62

7237

96685066

Returns: 36
98

24

14

644266

93084212

848

2

886

887

Returns: 3747005
89

503

190723

197133

197136

3

41735952

45134969

45251006

Returns: 151887067
91

516

17138753

29994

99885703

87235195

15550

464193

99999969

Returns: 626497128
91

9

961

1868836

1877407

0

21804053

19560738

21804072

Returns: 387450494
5

1807

10

991272

991277

15011

94078763

94078318

94078794

Returns: 9
94

5890

6596

6555

6601

3

89

115

22899

Returns: 866705549
34

578

539

105

579

9095771

9094954

9095726

9095778

Returns: 824341644
32

99995914

519646

1

99999999

94092325

63092760

1686003

94104971

Returns: 146176932
27

99999444

99999401

99522069

99999445

468

22902

3991190

3998581

Returns: 64485888
99

1956928

2042

30846

1961891

2542236

2516395

7792

2554926

Returns: 15311622
100

31

99443295

98730309

99746173

1363

5

29476843

97756276

Returns: 662759521
16

44

494

99999346

99999347

99331510

11730060

99967350

99967362

Returns: 56866
97

99996639

99998607

13601

99998611

1786906

4

99518142

99999995

Returns: 465308747
94

3242565

98878511

99985555

99985557

81566066

1285832

72843058

86913914

Returns: 610835671
98

96677737

253

97917186

99978201

32

899

890

901

Returns: 894495751
12

99935922

2988024

99999981

99999993

99999517

106

99991633

99999997

Returns: 940
99

2970206

2225676

2982442

2982525

99999792

99885417

99999950

99999993

Returns: 872954992
97

957715

49898402

7874531

49898405

59323

86

90339168

90342884

Returns: 730614453
21

99832832

99999907

43135660

99999955

104

25

1879

1988

Returns: 131072
100

23209566

12017188

23260307

23260507

99181135

7916843

567632

99798762

Returns: 949296359
86

10094

10054

4

10097

99999197

99133067

129

99999999

Returns: 991742525
48

91

97097697

97093638

97097871

99105075

99128212

97872072

99136090

Returns: 715441925
90

4824376

69

3805423

4838937

265

1

117

268

Returns: 146712356
94

58944002

58943619

12678509

58944049

12396910

13664202

10326289

13664205

Returns: 892070758
82

99971502

99999997

99999994

100000000

9126

141166

483932

99993734

Returns: 134562469
64

7

26

109342

161617

7274

87188

84051048

99999999

Returns: 551427948
90

87508749

87513862

74033183

87517158

4128

107

4649

4726

Returns: 893930013
7

448

7

239

452

50978

99999990

71002834

99999994

Returns: 8
98

590558

99999623

99103

99999716

99428003

10065738

0

99431884

Returns: 665805613
98

99997856

984002

269071

99997870

66623222

5228258

70478943

70615958

Returns: 881204576
95

1137212

939

865098

1137222

82447312

8314

95318815

95318816

Returns: 213862976
89

39675767

41

89584712

89584753

298853

60368

87

342242

Returns: 587875486
13

387

28

200

955

98989284

122200

98989386

98989512

Returns: 1791
6

0

40

801

802

97482608

97480531

85484079

97482610

Returns: 14
42

99998314

99999540

99998946

99999999

2

2

374465

650667

Returns: 584287653
71

96902

58659

97055

97455

1398

431

665

1399

Returns: 426528965
8

99996686

246

99824747

99996698

93106091

71683678

66657542

99340567

Returns: 50
99

0

1485813

1478538

1491933

99869215

99742626

2484870

99870830

Returns: 559228270
100

2035836

8731367

8453452

8743786

280

1

2325

7029

Returns: 391240673
17

11

28026

81424378

98618081

19974

444493

14

5024003

Returns: 0
29

99999812

316893

224

99999938

3623278

3623222

2064557

3623284

Returns: 251192832
95

0

96854750

96855827

96855841

415

99999519

6

99999535

Returns: 256535942
230

1691997

1693284

16

1693289

1258326

80

52642244

99999882

Returns: 450090203
1999

99963587

4136983

64677929

99999920

996036

15197

8042956

8042958

Returns: 451062168
1871

519447

578

885

99999991

271

5224

55

5283

Returns: 978349492
354

8221047

319454

41691645

41691726

14892603

98

69564854

69597383

Returns: 186836456
1994

105170

1871573

3

99999999

78122843

71406096

78177246

78180398

Returns: 864440352
53

25337

99989177

99998859

99999952

14

47422

91

47553

Returns: 215243062
1117

428

15321946

15329089

15329355

671696

40334

44927

45174450

Returns: 806930894
558

0

6726

99465533

99465726

5

99999991

9

100000000

Returns: 245984446
360

1272711

68774853

68774842

68774863

87677

7250074

99999989

99999997

Returns: 153261027
1971

95961544

2242

99999493

99999494

98258440

99998222

627591

99998268

Returns: 517853875
1973

4

86131233

99999990

99999992

14

450587

25786

99999991

Returns: 737523693
442

1

104

93800567

96047718

0

13337901

13312069

13338048

Returns: 458089919
66

1

318

99614359

99614781

289595

617911

290758

94195907

Returns: 196980297
1996

56799137

56165910

56799147

56799152

99999998

123

99999981

99999999

Returns: 187429315
940

10

97001866

97001870

97001872

847

5463175

213

5973498

Returns: 66344081
2000

99525775

178931

12068995

99999993

27

99868314

1953

99999400

Returns: 779595850
3

970643

1268

1460

977965

193261

6716995

6689222

6717024

Returns: 0
1825

3822017

2728375

5721112

19332854

301068

1

252

301075

Returns: 664977044
19

39945

99938744

99774919

99999985

6

161

99999907

99999958

Returns: 226788
124

7004

99709588

219

99999963

99999901

75479806

99999745

99999902

Returns: 786395926
9

63121

81197625

92632057

99998864

1650

6444

46

99613372

Returns: 0
1710

26644

94429366

94436082

94436164

57882551

70486821

70049520

70495982

Returns: 701739621
1949

0

1778698

74129316

99813485

99876685

77

64651

99876687

Returns: 996986878
1733

46105856

99979229

99727147

100000000

23

3825

99816321

99999997

Returns: 914112425
43

152180

3572

95784

152235

18355

99822334

32069

99999666

Returns: 858469117
1892

99245900

30375393

12394418

99277487

15080

159359

72055639

99961143

Returns: 258116371
1972

99996185

99792513

99996148

99996191

446687

451678

451979

452106

Returns: 726087210
61

99999823

9

0

99999999

99871234

99999208

99999223

99999224

Returns: 216325221
943

1432

79

17893

62267947

21165565

99697141

1696490

99754171

Returns: 208164184
1937

94344895

3

99994963

99994964

97272271

99969292

12

99969498

Returns: 834517811
9

99992923

99880688

99997993

99999676

490

99830547

99875520

99899727

Returns: 0
1975

148

113

99997565

99999974

4314

17927

25

18346

Returns: 670082773
963

99679147

2294

4837

99679149

99973709

99999619

99989428

99999802

Returns: 248896922
51

190

1623

15485

99997368

363

2108

112

99999129

Returns: 122391439
393

29693260

1755

99101974

99971306

1

5

47293

47405

Returns: 292329615
56

17

6617835

6031461

6618073

0

69456443

33014642

99935924

Returns: 968217503
1405

99999829

99999809

93538

99999832

199

82337121

300743

86013722

Returns: 690611042
2000

54939

2881123

1880536

61933442

19812255

19799604

2401

19812257

Returns: 263726397
4

377926

22

232

377947

81471937

91756670

91756669

91756674

Returns: 0
1996

80101

168

1302

119037

99933008

190

114095

99960157

Returns: 639462659
1109

99971599

20

2009101

99999974

19

99999929

49415348

99999953

Returns: 915710694
1084

99786046

99785855

99786095

99786097

1246

3977

99988131

100000000

Returns: 747442868
1872

89545636

77316063

39

95949467

3578

264

99895169

99999339

Returns: 688509493
1687

4372623

95991238

0

96508081

4851

230280

1557

99999501

Returns: 400411207
1997

98110498

11

724

98110565

99839514

96238175

99994620

99998643

Returns: 587805559
7

1806

99999829

75395416

99999880

49

100731

104863

104881

Returns: 36
1997

38

735761

866462

99951713

71347

107203

106134

107639

Returns: 895841116
99

99805395

31396296

6

99805816

29475

1194

52483

52533

Returns: 95792820
9

16438596

26

2500662

16438782

55

3

60

24691814

Returns: 0
1931

99999577

115

99996779

99999578

4655156

4703830

3315413

4703862

Returns: 119746182
2000

16441363

9810846

1

16448857

31

99696205

99688667

99710074

Returns: 748638337
2000

0

24

1499

421325

1000

97968986

97971663

97971665

Returns: 35662270
2000

1866348

98878705

204

99999956

1216348

99999034

99998575

99999512

Returns: 623719249
2000

0

404165

1596

65382592

63103143

13

71732875

71732879

Returns: 744371154
2000

4570035

69820546

192737

99878254

370

66438332

99136777

99136811

Returns: 181733766
2000

99999913

22336721

4427357

99999960

5848400

85847495

94108249

94108624

Returns: 840806335
2000

9500

1790

61579

84862

99389885

45676

444122

99999598

Returns: 500886049
2000

46915644

46913010

456

46915646

12169

99956998

27

99999356

Returns: 104894520
2000

2500

99989092

99998926

99999778

99999180

99994777

233208

100000000

Returns: 65214964
2000

95917065

4317711

59

99999963

64464845

64464317

8

64464852

Returns: 845387704
2000

16553248

14630836

2578394

16556117

22851667

237

30741414

86099375

Returns: 244380733
2000

230789

231081

226947

231431

99999107

99620104

90522060

99999877

Returns: 300556681
2000

3620

89

39308095

39308101

737

236962

1944485

1944573

Returns: 537399929
2000

99999991

99999992

44686135

99999996

46530

99986169

99724543

99999998

Returns: 461778592
2000

62817018

47265420

9

62817126

99981146

9009

42

99981433

Returns: 588295158
2000

27126338

26961714

27084569

27313808

941966

68537827

3561

99999944

Returns: 124817514
2000

80

14623

10940

14631

12

99852424

861

99985874

Returns: 601664442
2000

20419

207

20397

20422

5

99598046

99143329

99598434

Returns: 195737300
2000

99364798

99379892

6

99379911

2541

44110034

99999749

99999750

Returns: 486349121
2000

4197643

21167767

99086814

99998796

99999706

2654

72

99999709

Returns: 955537376
2000

99999983

99999939

99560126

99999990

4322993

7171104

2673

7712161

Returns: 969836912
2000

2203441

13097330

74374894

74374895

8

1

21802

21822

Returns: 913928581
2000

32716

99977939

4169848

99977985

56694

618341

618130

618343

Returns: 487673711
2000

99968585

97517322

57917

99999997

99968567

99968624

14170

99968636

Returns: 282809902
2000

8

47019482

206

94849450

852274

48

2369794

2446197

Returns: 92309808
2000

99999613

99999956

1519

100000000

99912812

99912803

98145456

99912816

Returns: 506539788
2000

54206317

3323636

50264992

54206962

13

21

62060847

62060854

Returns: 498175764
2000

4692554

1564885

4699344

4699484

478328

478323

12

478333

Returns: 325410523
2000

59

99991350

99999049

99999969

287833

173

287850

287860

Returns: 899835837
2000

95295063

98489185

94925400

99999970

82010059

99981022

92107

99999956

Returns: 881383752
2000

1926891

18147

49

5459847

99703913

99995320

99885764

99999761

Returns: 218484190
2000

99999871

99999531

99999976

99999998

99989556

87238704

94483659

99989558

Returns: 566552541
2000

474222

802764

99432452

99999956

99991844

61967868

35828

99991845

Returns: 415865246
2000

96012695

333556

68038518

99999806

47758539

99856639

99999898

99999997

Returns: 254085860
2000

99999099

99999273

33385024

100000000

18965491

18966862

18966937

18966941

Returns: 353418454
2000

79879966

492

5349639

100000000

1249

123

15281

99999999

Returns: 224676743
2000

29

99643233

99910344

99914358

99999347

99709163

99544392

99999573

Returns: 925380695
2000

0

83509125

83506493

83509249

4234

10141

3822

11723

Returns: 856385798
2000

82751752

26901

6532779

99232329

3670336

69839

49

3671049

Returns: 847281875
2000

0

17

1

43438

99434455

98661584

99253417

99434458

Returns: 464343136
2000

2818

21022741

27545913

27546630

214

95743190

96388304

96388328

Returns: 293842123
2000

93669895

93691924

80222758

93691931

0

189097

27

189160

Returns: 817316221
2000

167

7

99998257

99998272

99985181

357686

86043

99999763

Returns: 601162223
2000

1278

99857047

14

99999998

1724

56989610

53719

98715271

Returns: 480324244
2000

17284206

2

271674

20830714

98082014

96437347

5985527

98082015

Returns: 279554078
2000

14816027

14816089

62406

14816100

48636812

48715661

48721950

48721991

Returns: 781065213
2000

2520335

242

99993331

99993337

99618740

92246691

99618570

99618748

Returns: 437080791
2000

99334060

99999998

99999835

100000000

2

47179084

46186873

47179099

Returns: 991904332
2000

86248734

86247929

5885

86248735

7321

2644835

99999953

99999957

Returns: 797165969
2000

2346812

2300054

50

2346843

2

386

2350969

99996745

Returns: 286256980

Statistics

Problem Statement for "PQHulls"

Problem Statement

Definition

Notes

Constraints

Examples