Statistics

Problem Statement for "TwiceTwiceTree"

Problem Statement

Given a tree T, we can produce a new tree T' as follows: T' will contain the entire tree T. Additionally, for each vertex x in T, add a new vertex to T' and attach it to x. We will call this procedure growing the tree.


You are given ints N, D, and P. Start with a tree that consists of a single vertex. Grow this tree N times to produce a tree with 2^N vertices. In that tree, count all simple paths of length D, and return that count modulo the prime P.


The length of a simple path is the number of edges it contains. Two simple paths are considered different if they contain a different set of edges. In other words, the direction in which the path is traversed does not matter.

Definition

Class:
TwiceTwiceTree
Method:
sumup
Parameters:
int, int, int
Returns:
int
Method signature:
int sumup(int N, int D, int P)
(be sure your method is public)

Constraints

  • N will be between 1 and 1,000,000,000, inclusive.
  • D will be between 1 and 500, inclusive.
  • P will be between 503 and 1,000,000,009, inclusive.
  • P will be a prime.

Examples

  1. 3

    3

    1000000007

    Returns: 8

    The eight paths are shown in orange in the figure below. You may also note that the size of the nodes corresponds to their "generation": the largest node is the original one, the smallest nodes are the ones that were added when the tree grew for the last time.

  2. 1

    10

    503

    Returns: 0

    There is no path of length 10 because the tree is too small.

  3. 10

    1

    503

    Returns: 17

  4. 10

    5

    1000000009

    Returns: 21352

  5. 987654321

    500

    1000000009

    Returns: 420937613

  6. 1000000000

    500

    1000000009

    Returns: 756135781

  7. 1000000000

    500

    1000000007

    Returns: 808901085

  8. 1

    1

    503

    Returns: 1

  9. 1

    500

    1000000009

    Returns: 0

  10. 1

    2

    866839931

    Returns: 0

  11. 1

    3

    372207301

    Returns: 0

  12. 2

    3

    569502473

    Returns: 1

  13. 1

    4

    710169347

    Returns: 0

  14. 2

    4

    216156329

    Returns: 0

  15. 3

    4

    201200267

    Returns: 4

  16. 1

    5

    455850667

    Returns: 0

  17. 2

    5

    57396611

    Returns: 0

  18. 3

    5

    218536873

    Returns: 1

  19. 4

    5

    981071129

    Returns: 17

  20. 996176646

    82

    295528853

    Returns: 164871635

  21. 599995667

    298

    1093

    Returns: 336

  22. 32831921

    240

    517686007

    Returns: 302802726

  23. 68704459

    177

    842795669

    Returns: 151826056

  24. 56219351

    418

    151065973

    Returns: 20944967

  25. 631683537

    432

    354982039

    Returns: 92464862

  26. 249796914

    485

    522299473

    Returns: 371104135

  27. 150332582

    496

    881

    Returns: 253

  28. 78702324

    257

    997

    Returns: 509

  29. 434093214

    33

    116505133

    Returns: 35980769

  30. 157615801

    428

    667338983

    Returns: 299674017

  31. 798228727

    152

    618111761

    Returns: 398974976

  32. 217512668

    154

    618447871

    Returns: 94520467

  33. 208755224

    342

    483177313

    Returns: 172911644

  34. 116976364

    15

    540965231

    Returns: 71128062

  35. 333114826

    47

    823

    Returns: 817

  36. 690344727

    289

    1039

    Returns: 326

  37. 54089080

    151

    1451

    Returns: 240

  38. 118468400

    225

    433791287

    Returns: 199868461

  39. 799417851

    319

    575151589

    Returns: 566410077

  40. 740407256

    498

    286721437

    Returns: 46515061

  41. 750126598

    500

    568114787

    Returns: 111628757

  42. 584476627

    495

    1453

    Returns: 978

  43. 195091279

    496

    153046193

    Returns: 60669869

  44. 700986372

    494

    220640507

    Returns: 125936433

  45. 739772507

    491

    856731341

    Returns: 37753935

  46. 982033859

    492

    541385497

    Returns: 289034474

  47. 954074547

    491

    97953049

    Returns: 73733881

  48. 315967021

    498

    907052011

    Returns: 241678695

  49. 975768551

    500

    207205799

    Returns: 38582858

  50. 65627166

    495

    331940503

    Returns: 154665800

  51. 900548742

    500

    122871997

    Returns: 104208706

  52. 791316699

    496

    473609707

    Returns: 66801982

  53. 12704927

    500

    869154947

    Returns: 25398883

  54. 694973415

    496

    74597087

    Returns: 29030399

  55. 183722895

    491

    506566213

    Returns: 185754294

  56. 9403990

    492

    670159079

    Returns: 471188266

  57. 950941965

    493

    306266549

    Returns: 50424396

  58. 42616911

    499

    727

    Returns: 350

  59. 596121131

    496

    1187

    Returns: 1025

  60. 999932543

    272

    632198143

    Returns: 465863084

  61. 999933772

    148

    696185227

    Returns: 460222327

  62. 999947413

    371

    287835259

    Returns: 72426104

  63. 999971049

    136

    269956657

    Returns: 204651735

  64. 999917815

    402

    1283

    Returns: 1233

  65. 999939511

    457

    6488887

    Returns: 212900

  66. 999989346

    245

    93732103

    Returns: 4399657

  67. 999987950

    92

    667699069

    Returns: 491487008

  68. 999952268

    373

    1259

    Returns: 924

  69. 999919528

    91

    29142499

    Returns: 16377807

  70. 999940711

    151

    853

    Returns: 244

  71. 999958313

    421

    908396663

    Returns: 479311572

  72. 999907325

    416

    289508519

    Returns: 250916422

  73. 999964458

    117

    258356561

    Returns: 2103273

  74. 999925300

    57

    385187629

    Returns: 170518884

  75. 999907352

    23

    792064709

    Returns: 582997204

  76. 999975217

    279

    569

    Returns: 199

  77. 999904531

    289

    255132433

    Returns: 75729717

  78. 999997179

    3

    636508841

    Returns: 603630913

  79. 999991060

    157

    262134539

    Returns: 33146993

  80. 999983056

    498

    1361

    Returns: 778

  81. 999953008

    500

    1277

    Returns: 665

  82. 999910606

    491

    829

    Returns: 625

  83. 999924077

    492

    448350659

    Returns: 35435408

  84. 999947297

    491

    1237

    Returns: 872

  85. 999901614

    500

    949040383

    Returns: 303062995

  86. 999916892

    499

    1471

    Returns: 251

  87. 999938858

    498

    307469257

    Returns: 42857199

  88. 999986524

    499

    482771687

    Returns: 274744581

  89. 999971123

    496

    947

    Returns: 226

  90. 999973417

    499

    919

    Returns: 256

  91. 999945670

    495

    317924729

    Returns: 220102043

  92. 999952647

    492

    272217859

    Returns: 102873183

  93. 999926910

    494

    107775853

    Returns: 101455793

  94. 999993030

    494

    166827781

    Returns: 15882301

  95. 999911092

    498

    250178839

    Returns: 195190896

  96. 999995974

    497

    722924459

    Returns: 467352671

  97. 999946494

    491

    34676233

    Returns: 32800355

  98. 999927581

    492

    294210751

    Returns: 121259636

  99. 999982743

    498

    345992627

    Returns: 305792273

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: