Statistics

Problem Statement for "ShrooksOnTheBoard"

Problem Statement

A K-shrook is a fairy chess piece that can move horizontally in both directions for at most K squares. Here is an illustration of 2-shrook possible moves:



Two K-shrooks attack each other if one of them can reach the other shrook's square in one move. You are given a board with H rows and W columns. Find out the number of ways to place an arbitrary positive amount of K-shrooks on this board so that no two of them attack each other. Return this number modulo 100003.

Definition

Class:
ShrooksOnTheBoard
Method:
count
Parameters:
int, int, int
Returns:
int
Method signature:
int count(int K, int H, int W)
(be sure your method is public)

Constraints

  • K will be between 1 and 1,000,000,000, inclusive.
  • H will be between 1 and 1,000,000,000, inclusive.
  • W will be between 1 and 1,000,000,000, inclusive.

Examples

  1. 1

    1

    3

    Returns: 4

    The possible placements are "S..", ".S.", "..S" and "S.S".

  2. 1

    2

    2

    Returns: 8

    There can not be more than 1 shrook in a row.

  3. 3

    4

    9

    Returns: 56963

  4. 34

    83489

    98433

    Returns: 98118

    random medium test

  5. 65

    93284923

    819847362

    Returns: 94567

    random big test for MatrixMul

  6. 212

    187342874

    992837462

    Returns: 92273

    random big test for DP

  7. 1

    1

    1

    Returns: 1

  8. 1000000000

    1

    1

    Returns: 1

  9. 1000000000

    2

    2

    Returns: 8

  10. 1

    1000000000

    1

    Returns: 89147

  11. 1

    1

    1000000000

    Returns: 89458

  12. 2

    1

    1000000000

    Returns: 54934

  13. 70

    545

    983454345

    Returns: 98745

  14. 140

    342

    999999999

    Returns: 76639

  15. 5000

    1000000000

    1000000000

    Returns: 3976

  16. 2000

    49823838

    999999997

    Returns: 19060

  17. 1500

    2391382

    999999980

    Returns: 99763

  18. 1000

    39232848

    999999384

    Returns: 50828

  19. 3

    6

    10

    Returns: 17034

  20. 10

    10

    10

    Returns: 46502

  21. 1

    6

    7

    Returns: 58074

  22. 10

    10

    2

    Returns: 59048

  23. 5

    1

    3

    Returns: 3

  24. 8

    8

    4

    Returns: 90615

  25. 2

    6

    6

    Returns: 26664

  26. 2

    2

    7

    Returns: 360

  27. 5

    9

    1

    Returns: 511

  28. 7

    9

    3

    Returns: 62137

  29. 8

    5

    391

    Returns: 66499

  30. 109

    45811459

    997358662

    Returns: 50340

  31. 9483852

    999999951

    7467

    Returns: 39881

  32. 7301070

    3

    1870145

    Returns: 3250

  33. 3

    999997154

    6

    Returns: 62485

  34. 5959

    999789297

    828846743

    Returns: 99532

  35. 823861815

    999990198

    999999903

    Returns: 36225

  36. 95

    5644065

    5

    Returns: 15850

  37. 1

    6

    991629016

    Returns: 38175

  38. 1

    990974349

    8

    Returns: 57113

  39. 43007

    175986251

    30775288

    Returns: 34846

  40. 6473

    994511433

    808

    Returns: 10135

  41. 1

    999999992

    688565

    Returns: 5038

  42. 169

    72

    815607

    Returns: 22072

  43. 6423855

    580416

    999372813

    Returns: 3291

  44. 39582715

    67

    7

    Returns: 96128

  45. 23694087

    999999998

    644172

    Returns: 814

  46. 88339

    7638368

    369516

    Returns: 33757

  47. 1000000000

    999999993

    88

    Returns: 36179

  48. 999999998

    1000000000

    1000000000

    Returns: 97890

  49. 1

    5

    999999910

    Returns: 46141

  50. 2

    999999996

    999999324

    Returns: 86115

  51. 3

    999999996

    999604058

    Returns: 17610

  52. 4

    6

    999999199

    Returns: 75142

  53. 5

    55181802

    999999622

    Returns: 336

  54. 6

    60919124

    999999232

    Returns: 46816

  55. 7

    999999512

    999999080

    Returns: 12844

  56. 8

    104

    999999961

    Returns: 17052

  57. 9

    999911122

    999510962

    Returns: 49634

  58. 10

    999999973

    999999886

    Returns: 93839

  59. 24

    98

    999999957

    Returns: 37015

  60. 79

    5067

    536870911

    Returns: 48191

  61. 56

    999999504

    999640520

    Returns: 51042

  62. 13

    996830971

    536870911

    Returns: 97418

  63. 74

    999291196

    999999926

    Returns: 2790

  64. 20

    851063055

    536870911

    Returns: 22862

  65. 78

    999206276

    999999114

    Returns: 71029

  66. 54

    863573

    536870911

    Returns: 48608

  67. 45

    999998323

    999999993

    Returns: 18498

  68. 14

    999190741

    536870911

    Returns: 87126

  69. 70

    999926779

    999979761

    Returns: 3098

  70. 36

    996063264

    536870911

    Returns: 47467

  71. 31

    16693

    999421426

    Returns: 11632

  72. 57

    906502232

    536870911

    Returns: 71781

  73. 68

    999999994

    999994613

    Returns: 46988

  74. 91

    999999495

    536870911

    Returns: 42265

  75. 45

    996415526

    999972673

    Returns: 71247

  76. 74

    14

    536870911

    Returns: 95826

  77. 55

    178006

    999994463

    Returns: 75358

  78. 73

    999996294

    536870911

    Returns: 21914

  79. 122

    87363366

    999955313

    Returns: 40542

  80. 104

    999456730

    536870911

    Returns: 74426

  81. 106

    474881719

    999937976

    Returns: 73674

  82. 168

    87065

    536870911

    Returns: 78794

  83. 104

    161

    999985356

    Returns: 73623

  84. 115

    44634

    536870911

    Returns: 80331

  85. 132

    999999769

    999999981

    Returns: 36498

  86. 141

    999999930

    536870911

    Returns: 10811

  87. 154

    97

    999999953

    Returns: 74522

  88. 183

    999999997

    536870911

    Returns: 92918

  89. 147

    9248029

    999999995

    Returns: 23475

  90. 121

    821909817

    536870911

    Returns: 62322

  91. 150

    605651454

    999730451

    Returns: 98357

  92. 171

    450

    536870911

    Returns: 18481

  93. 190

    3615

    999999999

    Returns: 74972

  94. 119

    3669763

    536870911

    Returns: 10871

  95. 108

    734366

    999999707

    Returns: 46783

  96. 174

    74

    536870911

    Returns: 9634

  97. 117

    583984

    999999995

    Returns: 64971

  98. 119

    23303

    536870911

    Returns: 88006

  99. 195

    256616

    999999969

    Returns: 68799

  100. 185

    6287

    536870911

    Returns: 33923

  101. 154

    668877

    999999958

    Returns: 86828

  102. 144

    96566419

    536870911

    Returns: 74639

  103. 141

    946310181

    999046268

    Returns: 55331

  104. 133

    7770

    536870911

    Returns: 22532

  105. 190

    999142361

    999999998

    Returns: 63480

  106. 172

    996329878

    536870911

    Returns: 17817

  107. 160

    988663414

    999861792

    Returns: 36860

  108. 108

    850

    536870911

    Returns: 69527

  109. 139

    6100

    999992067

    Returns: 46563

  110. 194

    999999913

    536870911

    Returns: 37906

  111. 126

    67982555

    999999994

    Returns: 82411

  112. 170

    183905

    536870911

    Returns: 1450

  113. 153

    999391855

    999999992

    Returns: 46539

  114. 191

    11358

    536870911

    Returns: 42950

  115. 130

    999992464

    999993485

    Returns: 71105

  116. 166

    999995933

    536870911

    Returns: 29709

  117. 163

    850

    999999996

    Returns: 58285

  118. 151

    999999994

    536870911

    Returns: 43662

  119. 234

    597370

    999819915

    Returns: 12952

  120. 205

    651

    536870911

    Returns: 47877

  121. 251

    995814999

    999985788

    Returns: 74864

  122. 224

    366301249

    536870911

    Returns: 95550

  123. 288

    999999499

    999986880

    Returns: 83333

  124. 241

    1

    536870911

    Returns: 66755

  125. 234

    1000000000

    999999918

    Returns: 7447

  126. 294

    563704

    536870911

    Returns: 30823

  127. 259

    914953220

    999999926

    Returns: 46898

  128. 203

    48159

    536870911

    Returns: 49443

  129. 282

    999999904

    999953884

    Returns: 18931

  130. 249

    30649220

    536870911

    Returns: 88733

  131. 240

    8

    999996087

    Returns: 28326

  132. 233

    999949920

    536870911

    Returns: 64588

  133. 238

    999219541

    999993271

    Returns: 42902

  134. 282

    90

    536870911

    Returns: 70427

  135. 214

    13163806

    999999994

    Returns: 85981

  136. 225

    63820

    536870911

    Returns: 78762

  137. 210

    999992590

    999999994

    Returns: 16471

  138. 242

    999999590

    536870911

    Returns: 13060

  139. 326

    6431

    999999501

    Returns: 17236

  140. 336

    996446976

    999994367

    Returns: 22418

  141. 413

    771

    999737218

    Returns: 1060

  142. 422

    813996332

    999990180

    Returns: 48404

  143. 321

    629

    999995449

    Returns: 3969

  144. 448

    479484

    999191570

    Returns: 44557

  145. 485

    8

    999950557

    Returns: 81175

  146. 303

    895315

    999992967

    Returns: 48190

  147. 443

    64

    1000000000

    Returns: 39952

  148. 442

    780

    999991763

    Returns: 66610

  149. 861

    374987345

    999509357

    Returns: 61453

  150. 930

    519045

    999999992

    Returns: 61993

  151. 1398

    999907737

    999999999

    Returns: 52835

  152. 857

    997359090

    999923302

    Returns: 52372

  153. 841

    999923238

    999997480

    Returns: 33558

  154. 884

    999204245

    999901442

    Returns: 40836

  155. 567

    993883212

    999933539

    Returns: 57350

  156. 563

    997853007

    999999996

    Returns: 29191

  157. 561

    38160

    999931506

    Returns: 41138

  158. 535

    993904568

    999997334

    Returns: 38220

  159. 61962

    999992872

    999999295

    Returns: 59374

  160. 9582

    45644104

    999999623

    Returns: 28427

  161. 5778

    999325857

    1000000000

    Returns: 76117

  162. 8276

    5

    999999934

    Returns: 11654

  163. 46757

    339404

    999999992

    Returns: 93034

  164. 4630

    999999995

    999043686

    Returns: 77497

  165. 7913

    169866

    999991554

    Returns: 77575

  166. 26250

    83

    999447596

    Returns: 11512

  167. 4654

    40271895

    999999957

    Returns: 50506

  168. 93404

    999995710

    999990853

    Returns: 52567

  169. 411993000

    90873

    999999996

    Returns: 63203

  170. 478432

    902337243

    999622961

    Returns: 63396

  171. 999990049

    9143

    999886942

    Returns: 85678

  172. 639700194

    999415087

    999970171

    Returns: 86646

  173. 959717274

    6000

    999943759

    Returns: 37169

  174. 999996969

    9928

    999999457

    Returns: 64357

  175. 999991464

    155

    999999361

    Returns: 71509

  176. 603861417

    6

    999999997

    Returns: 57252

  177. 105309206

    992330207

    999999999

    Returns: 93058

  178. 999999996

    999999790

    999999862

    Returns: 65165

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: