Statistics

Problem Statement for "ColorfulLineGraphs"

Problem Statement

Bob is going to create a graph with N nodes. The graph will be constructed in two steps. First, Bob will take N isolated vertices, label them 1 through N and color each of them using one of K colors. Then, Bob will add some directed edges to the graph. For each i between 2 and N, inclusive, Bob may choose a single value j < i such that the nodes i and j have different colors. If he does, he will add the edge from i to j to his graph. Note that Bob may choose not to add any edge from node i, even if there are some valid choices of j.

Two graphs are considered the same if they have the same node colors and the same set of edges.

You are given the longs N and K. You are also given an int M. Compute and return the number of different graphs Bob may construct, modulo M.

Definition

Class:
ColorfulLineGraphs
Method:
countWays
Parameters:
long, long, int
Returns:
int
Method signature:
int countWays(long N, long K, int M)
(be sure your method is public)

Constraints

  • N will be between 1 and 1,000,000,000,000 (10^12), inclusive.
  • K will be between 1 and 1,000,000,000,000 (10^12), inclusive.
  • M will be between 2 and 1,000,000 (10^6), inclusive.

Examples

  1. 3

    2

    100000

    Returns: 24

    The 24 different graphs are shown below. In each picture, the vertices have labels 1, 2, 3 from the left to the right.

  2. 15

    3

    1000000

    Returns: 510625

  3. 100000

    100000

    999999

    Returns: 185185

  4. 1000000000000

    6

    1000000

    Returns: 109376

  5. 5000

    1000000000000

    314159

    Returns: 202996

  6. 479490454733

    261349224448

    848601

    Returns: 188578

  7. 481274701232

    927843027765

    457796

    Returns: 114449

  8. 901590959996

    599844610260

    847419

    Returns: 535212

  9. 560729190012

    550615278251

    270222

    Returns: 135111

  10. 538436296825

    101295900677

    762216

    Returns: 95277

  11. 225640

    789563495545

    37602

    Returns: 14623

  12. 163808

    848788449304

    661686

    Returns: 441124

  13. 839918

    435737878813

    569804

    Returns: 427353

  14. 427721

    163923716305

    276842

    Returns: 138421

  15. 117668

    319925035533

    591244

    Returns: 443433

  16. 22

    598

    210

    Returns: 70

  17. 733

    389

    902

    Returns: 451

  18. 588

    919

    987

    Returns: 658

  19. 719

    519

    716

    Returns: 537

  20. 17

    871

    188

    Returns: 103

  21. 578136583404

    968653

    767854

    Returns: 383927

  22. 464617359295

    114915

    747492

    Returns: 186873

  23. 400540797706

    144130

    420084

    Returns: 93352

  24. 50068332331

    987436

    163970

    Returns: 131176

  25. 119651848333

    255949

    123840

    Returns: 17845

  26. 1

    1000000000000

    654321

    Returns: 561379

  27. 1000000000000

    1

    29810

    Returns: 1

  28. 5000000000

    5000000000

    100007

    Returns: 0

  29. 121412521512

    112141251512

    10

    Returns: 0

  30. 1000000000000

    100

    2

    Returns: 0

  31. 1000000000000

    1000000

    10

    Returns: 0

  32. 1000000000000

    444

    2

    Returns: 0

  33. 1000000000000

    1000000000000

    10

    Returns: 0

  34. 233333333333

    233333

    73

    Returns: 0

  35. 11

    13

    5

    Returns: 0

  36. 18973812574

    12398712544

    999999

    Returns: 976690

  37. 1

    58

    6

    Returns: 4

  38. 1000001

    6

    1000000

    Returns: 656256

  39. 1

    1000000000000

    5

    Returns: 0

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: