TopCoder Statistics - Problem Statement

Problem Statement

Fox Jiro has a rectangular grid with H rows and W columns (i.e., the grid has H*W cells in total). Initially, each cell in the grid contained the character '0'.

A row flip is an operation in which Jiro picks a row of the grid, and in that row he changes all '0's to '1's and vice versa. Similarly, a column flip is an operation in which Jiro does the same to a column of the grid. Jiro took the grid that contained '0's everywhere. He performed a row flip Rcount times, and then a column flip Ccount times. (It is possible that Jiro flipped the same row or column multiple times.) At the end, Jiro noticed that there are exactly S '1's in the grid.

You are given the ints H, W, Rcount, Ccount, and S. We are interested in the number of different ways in which Jiro could have flipped the rows and columns of the grid. Two ways of flipping are considered different if there is a row or a column that was flipped a different number of times. (That is, the order in which the rows and columns are flipped does not matter.) Return the number of different ways of flipping that match the given situation, modulo 555,555,555.

Definition

Class:: XorBoard
Method:: count
Parameters:: int, int, int, int, int
Returns:: int
Method signature:: int count(int H, int W, int Rcount, int Ccount, int S)
(be sure your method is public)

Constraints

H will be between 1 and 1,555, inclusive.
W will be between 1 and 1,555, inclusive.
Rcount will be between 0 and 1,555, inclusive.
Ccount will be between 0 and 1,555, inclusive.
S will be between 0 and H*W, inclusive.

Examples

2

2

2

2

4

Returns: 4

In two of the four ways, Jiro flips each row once, and then the same column twice. In the other two ways he first flips the same row twice, and then each column once.
2

2

0

0

1

Returns: 0

Without any flips, all cells still contain '0's, so S=1 is impossible.
10

20

50

40

200

Returns: 333759825

Rcount and Ccount may be greater than H and W.
1200

1000

800

600

4000

Returns: 96859710
555

555

555

555

5550

Returns: 549361755
1555

1555

1555

1555

1110000

Returns: 188078400
1555

1555

1555

1555

1186490

Returns: 337179150

60 possible choices for (odd rows, odd columns)
1555

1555

1554

1555

1186490

Returns: 0
1555

1555

1555

1554

1186490

Returns: 0
1555

1555

1554

1554

1186490

Returns: 324123885
1554

1554

1555

1555

1207458

Returns: 394435170

3109 choices
1

1

0

0

0

Returns: 1
1

1

0

0

1

Returns: 0
1

1

0

1

0

Returns: 0
1

1

0

1

1

Returns: 1
1

1

1

0

0

Returns: 0
1

1

1

0

1

Returns: 1
1

1

1

1

0

Returns: 1
1

1

1

1

1

Returns: 0
1000

1000

1555

1554

500000

Returns: 122698845
1000

1000

1554

1555

500000

Returns: 122698845
1000

1000

1554

1554

500000

Returns: 524992815
1000

1000

1555

1555

500000

Returns: 0
1554

1554

777

777

1207458

Returns: 417635946
1554

1554

776

777

1207458

Returns: 373603689
1554

1554

776

776

1207458

Returns: 0
1554

1554

776

777

1206681

Returns: 0
1178

1324

476

610

950628

Returns: 0
524

685

753

203

137820

Returns: 0
1497

1375

1552

750

1084410

Returns: 349781535
1460

985

440

972

1052811

Returns: 0
913

1043

1322

769

467978

Returns: 0
1303

1316

426

1454

409610

Returns: 0
344

1232

1089

1132

276096

Returns: 192597210
851

603

232

1380

123594

Returns: 497473695
1426

1241

418

443

1179169

Returns: 0
1208

427

679

1334

180471

Returns: 263854215
743

438

1278

217

105809

Returns: 539253540
1013

923

1412

1554

582452

Returns: 310847175
1147

319

1485

1433

198368

Returns: 226664775
762

185

131

1546

32975

Returns: 24082560
446

1374

1178

1040

196734

Returns: 0
803

929

1277

1253

460229

Returns: 0
1547

874

1237

161

934326

Returns: 0
1231

673

1467

1056

372063

Returns: 463051485
1107

5

396

1317

2265

Returns: 49295655
479

123

810

196

12413

Returns: 0
1016

226

1013

742

125000

Returns: 0
24

324

1186

441

3888

Returns: 429038865
1369

1196

927

400

1336365

Returns: 0
1410

1208

1023

1198

1093560

Returns: 461781090
1266

715

1078

213

558882

Returns: 0
372

1014

209

226

200508

Returns: 0
563

193

807

1068

52631

Returns: 538269525
1543

1484

1384

648

1352010

Returns: 155900610
691

720

1016

913

249165

Returns: 502548075
662

374

548

124

106924

Returns: 0
94

1068

1266

135

59524

Returns: 0
291

883

88

970

181678

Returns: 391586355
11

541

56

929

1089

Returns: 57637305
31

1336

1288

812

15833

Returns: 0
1198

1067

541

208

779646

Returns: 0
1328

172

1398

756

210012

Returns: 0
497

1500

1244

674

490911

Returns: 0
1517

288

1281

105

214053

Returns: 0
1268

1160

575

735

1086440

Returns: 0
1366

543

830

1542

335386

Returns: 327370635
1434

1072

516

1258

808804

Returns: 127680525
408

979

1244

299

76364

Returns: 0
253

299

52

1000

68893

Returns: 0
230

270

193

243

52254

Returns: 0
1072

1033

342

875

422956

Returns: 274245480
496

225

256

1091

0

Returns: 0
394

1342

276

76

528748

Returns: 0
175

979

707

1020

0

Returns: 0
1420

1286

1311

214

0

Returns: 0
647

548

980

306

0

Returns: 105502635
1547

1437

714

434

2223039

Returns: 0
86

835

159

694

0

Returns: 0
275

1390

66

1251

382250

Returns: 0
799

819

531

1435

654381

Returns: 0
299

961

1055

1553

287339

Returns: 0
708

365

721

262

258420

Returns: 0
1279

989

337

1482

0

Returns: 0
1507

1022

287

1246

1540154

Returns: 0
1391

1215

1267

431

0

Returns: 0
1162

1352

1301

492

0

Returns: 0
745

277

304

1228

17768

Returns: 0
1439

1169

359

1164

941288

Returns: 0
816

896

110

361

561048

Returns: 0
433

893

931

1374

124779

Returns: 177224265
1107

1257

403

1487

745130

Returns: 0
677

624

528

860

186474

Returns: 502991505
438

1127

223

943

246813

Returns: 539083710
688

1007

1551

10

256058

Returns: 0
1168

1207

1066

835

655682

Returns: 312696990
554

63

737

223

15696

Returns: 0
1554

1500

1398

1490

1581000

Returns: 29841795
1555

1555

1554

1554

0

Returns: 412213410
1555

1555

796

759

1051271

Returns: 176012145
1555

1554

1555

1554

2416470

Returns: 105127245
1555

1555

1555

1555

2410250

Returns: 243274149
1555

1555

1551

1551

1080020

Returns: 295720650
1555

1555

1555

1554

2418025

Returns: 435468645
1555

1555

1555

1555

500000

Returns: 548226225
1555

1555

1555

1555

0

Returns: 1
1554

1554

1554

1554

0

Returns: 430119541
1400

1400

700

700

980000

Returns: 411508080
1555

1555

1555

1555

1197612

Returns: 507723435
2

2

1

1

2

Returns: 4
1554

1554

1554

1554

2414916

Returns: 210254490
101

101

101

101

0

Returns: 1
1555

1555

1555

1555

3108

Returns: 109489770
10

2

10

1

10

Returns: 184756
1554

1554

1554

1554

1207458

Returns: 0

Statistics

Problem Statement for "XorBoard"

Problem Statement

Definition

Constraints

Examples