TopCoder Statistics - Problem Statement

Problem Statement

You are given a square board of size NxN. Each 1x1 cell will be colored either black or white. A rectangle on the board is called good if it contains only white cells. A good rectangle is called perfect if it doesn't lie completely within any other good rectangle.
Here's how the board will be colored. You are given ints M, X0, Y0, A, B, C and D. Generate lists X and Y, each of length M, using the following recursive definitions:
X[0] = X0 MOD N
X[i] = (X[i-1]*A+B) MOD N
Y[0] = Y0 MOD N
Y[i] = (Y[i-1]*C+D) MOD N
The board is initially entirely white. Then, for each i, the cell in column X[i] of row Y[i] is colored black. Return the number of perfect rectangles on the board.

Definition

Class:: PerfectRectangles
Method:: numberOfRectangles
Parameters:: int, int, int, int, int, int, int, int
Returns:: int
Method signature:: int numberOfRectangles(int N, int M, int X0, int A, int B, int Y0, int C, int D)
(be sure your method is public)

Notes

The same cell can be painted black multiple times.

Constraints

N will be between 1 and 2,000, inclusive.
M will be between 1 and 4,000,000, inclusive.
X0,Y0,A,B,C,D will each be between 0 and 2,000, inclusive.

Examples

5

1

2

0

0

2

0

0

Returns: 4

One black cell in the center.
4

4

0

1

1

0

1

1

Returns: 6

Black cells form the diagonal of the square.
1

1000000

1

2

3

1

4

7

Returns: 0

All cells are black.
10

20

4

76

2

6

2

43

Returns: 12
91

2511

440

936

329

467

709

150

Returns: 48
755

301848

431

823

931

993

491

952

Returns: 495
441

2029

876

699

698

404

370

292

Returns: 728
497

61594

885

18

273

642

893

868

Returns: 847
753

221641

862

225

704

126

660

656

Returns: 2171
597

157089

778

502

732

715

847

17

Returns: 909
366

102581

626

245

934

31

76

288

Returns: 81
496

141588

545

369

70

992

335

346

Returns: 360
679

206268

282

918

369

962

829

738

Returns: 2004
994

521050

525

907

80

102

517

532

Returns: 882
883

129679

364

642

304

964

921

682

Returns: 4631
71

4723

496

92

558

751

824

264

Returns: 363
1000

768327

40

27

559

632

743

333

Returns: 580
400

143875

326

990

161

76

427

953

Returns: 48
507

164521

570

197

749

177

901

931

Returns: 1163
472

2987

654

744

559

900

139

397

Returns: 715
460

53554

326

599

37

568

477

527

Returns: 828
341

109400

460

649

176

321

998

592

Returns: 131
331

33780

467

109

785

894

911

392

Returns: 2479
778

303044

505

791

611

296

419

790

Returns: 1764
359

8573

273

776

525

503

244

580

Returns: 3583
274

23230

329

90

465

192

670

975

Returns: 604
573

236433

777

560

612

445

175

441

Returns: 2045
848

213044

280

520

599

452

130

982

Returns: 137
88

1956

500

137

866

796

185

951

Returns: 238
252

3976

405

857

882

336

624

308

Returns: 14
919

556617

694

11

633

312

967

860

Returns: 4174
607

269387

843

983

508

598

702

70

Returns: 1563
911

152401

275

158

575

998

407

240

Returns: 8700
138

7744

172

696

152

165

902

823

Returns: 28
1000

215765

503

434

533

431

545

404

Returns: 119
195

2959

517

671

971

263

411

123

Returns: 138
599

173427

89

258

396

294

172

193

Returns: 3054
538

207245

251

781

651

285

690

96

Returns: 2239
363

14213

729

309

925

831

798

912

Returns: 4188
371

22691

159

122

202

173

140

481

Returns: 755
585

234242

4

236

413

266

638

32

Returns: 1463
204

7760

4

166

995

470

305

173

Returns: 44
837

637425

799

305

410

451

622

192

Returns: 129
384

99432

169

511

269

480

42

822

Returns: 25
823

676372

620

184

472

99

972

175

Returns: 9420
852

277311

167

48

943

12

923

542

Returns: 16
53

923

255

205

142

484

18

703

Returns: 160
114

317

803

235

141

256

944

391

Returns: 34
761

303988

603

693

681

140

538

278

Returns: 7190
69

1669

571

674

444

354

276

636

Returns: 22
901

805346

925

29

69

798

129

98

Returns: 947
60

2606

104

157

736

31

197

567

Returns: 8
932

480534

897

624

602

623

460

548

Returns: 238
473

202212

493

185

248

734

572

123

Returns: 605
314

65313

522

405

741

983

306

25

Returns: 985
203

7312

816

644

831

936

742

158

Returns: 39
950

90633

433

32

199

466

995

357

Returns: 127
353

22607

828

782

873

92

103

471

Returns: 2869
510

122389

324

823

676

80

534

386

Returns: 281
122

5224

344

518

348

625

193

536

Returns: 62
387

141409

678

705

102

588

9

884

Returns: 142
635

81873

826

274

924

553

561

205

Returns: 359
103

146

961

510

355

436

956

648

Returns: 368
657

115404

120

221

926

671

826

57

Returns: 41
3

2

0

2

2

1

1

2

Returns: 4
1676

469443

1738

950

1755

588

1002

403

Returns: 2323
1731

2384971

1809

1371

317

1077

1549

967

Returns: 4865
1818

738605

1571

571

380

917

1309

1437

Returns: 8131
1003

709929

757

1973

1770

1211

1012

1493

Returns: 23009
1257

640687

1698

458

1125

911

1866

1262

Returns: 2273
1401

411702

484

1909

543

478

609

198

Returns: 4708
1668

524728

1208

604

429

1708

845

333

Returns: 1774
1747

2943779

1900

409

1935

532

924

103

Returns: 22777
1945

2090182

1431

876

1688

1122

883

626

Returns: 21387
1205

1412820

1785

1024

1831

1277

1187

1430

Returns: 502
2000

6

511

1870

765

1323

167

1405

Returns: 23
2000

5

1438

1956

834

1465

1332

1677

Returns: 24
2000

9

375

601

36

1701

1396

1489

Returns: 50
2000

6

851

1460

1464

1186

1247

1039

Returns: 20
2000

4

1361

404

1306

813

331

1583

Returns: 19
2000

78

1460

447

446

757

1725

63

Returns: 373
2000

19

1446

1850

1967

1383

1750

1606

Returns: 23
2000

69

469

17

443

1104

810

993

Returns: 85
2000

56

1538

1955

1999

1262

651

1638

Returns: 213
2000

82

621

990

905

1455

1309

1758

Returns: 100
2000

538

213

1557

1372

1951

1405

362

Returns: 38
2000

718

1480

967

504

90

521

1859

Returns: 5328
2000

140

577

800

67

859

65

1601

Returns: 26
2000

982

1289

1626

1035

1686

1062

1759

Returns: 221
2000

591

1659

1981

1012

333

1462

1046

Returns: 3165
2000

5407

1418

1138

1328

1247

850

209

Returns: 114
2000

6692

50

827

1375

1406

56

251

Returns: 141
2000

6559

1677

1769

1283

91

658

142

Returns: 3446
2000

3332

1298

1610

703

687

740

1107

Returns: 12
2000

8145

1178

490

320

25

564

190

Returns: 26
2000

34825

670

1278

426

791

963

1981

Returns: 1862
2000

71763

1835

536

753

1352

1968

1790

Returns: 1095
2000

50604

1971

1368

1366

576

1613

1548

Returns: 138
2000

50076

833

1701

1281

301

21

260

Returns: 13617
2000

99436

354

1695

1819

964

682

1685

Returns: 28
2000

368644

1002

486

503

234

1984

1816

Returns: 1428
2000

803585

451

1082

94

378

1377

286

Returns: 219
2000

433771

1472

1533

67

336

1633

1758

Returns: 2955
2000

957330

1595

1312

37

699

1564

547

Returns: 683
2000

379869

237

1027

1286

1251

503

212

Returns: 942
2000

3153696

1187

848

1313

612

940

60

Returns: 116
2000

2788847

911

1614

4

1948

1400

1459

Returns: 66
2000

2630414

1073

1673

385

738

1052

1681

Returns: 3717
2000

1681664

1632

1905

1203

1614

1078

1586

Returns: 1106
2000

1440905

193

182

66

634

74

1346

Returns: 49
2000

4000000

653

1807

605

113

1466

848

Returns: 139
1999

4000000

1000

1

1

0

1

1

Returns: 1002995
2000

4000000

1500

1

1

500

1

1

Returns: 1003997
1999

91999

123

124

561

512

123

125

Returns: 22139
2000

100000

787

667

565

444

367

447

Returns: 1801
1997

3999999

42

19

17

17

13

98

Returns: 26727
2000

20

4

76

2

6

2

43

Returns: 133
1999

500000

788

1566

1596

1823

395

670

Returns: 9809
2000

4000000

234

123

432

1232

232

1234

Returns: 136
1999

4000000

61

17

19

11

7

3

Returns: 21460
2000

2000000

2

4

7

3

5

6

Returns: 270
1989

3500000

4

76

2

6

2

43

Returns: 463
2000

937421

432

769

232

123

212

943

Returns: 662
2000

200000

0

1

1

0

1

157

Returns: 37087

Statistics

Problem Statement for "PerfectRectangles"

Problem Statement

Definition

Notes

Constraints

Examples