Statistics

Problem Statement for "CrazyFunctions"

Problem Statement

In this problem, a function is any function that maps integers from 1 to n to integers from 1 to n. For example, if n=3, one possible function is the function g defined as follows: g(1)=1, g(2)=3, and g(3)=1.

We will use the notation f^(j)(x) to denote applying a function f to the input x exactly j times in a row. Formally:

  • for all valid x, f^(0)(x) = x
  • for all valid x and j, f^(j+1)(x) = f^(j)(f(x))

We will now formally define several new notations.

  • G(f,w) will be the set of all values f^(r)(x), where x is between 1 and n, inclusive, and r is greater than or equal to w.
  • S(f,w) will be the size of G(f,w).
  • Z(f) will be the minimum of S(f,w), taken over all nonnegative w.
  • A(y) will be the set of all functions f such that Z(f) = y.

You are given the int n and an int k. Compute and return the size of the set A(k), modulo 1,000,000,007.

Definition

Class:
CrazyFunctions
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int n, int k)
(be sure your method is public)

Constraints

  • n will be between 1 and 5,000, inclusive.
  • k will be between 1 and n, inclusive.

Examples

  1. 2

    1

    Returns: 2

    We have n = 2, which means that there are four different functions. Let's call them a, b, c, d as follows: a(1) = 1 and a(2) = 1 b(1) = 1 and b(2) = 2 c(1) = 2 and c(2) = 1 d(1) = 2 and d(2) = 2 Two of these functions (functions a and d) belong into the set A(1), so the correct return value is 2. The other two functions (b and c) belong into the set A(2).

  2. 2

    2

    Returns: 2

  3. 1

    1

    Returns: 1

  4. 3

    1

    Returns: 9

  5. 3

    3

    Returns: 6

  6. 5

    3

    Returns: 900

  7. 5000

    5000

    Returns: 541108809

  8. 5000

    1

    Returns: 534340435

  9. 3304

    1764

    Returns: 713379297

  10. 188

    65

    Returns: 843179173

  11. 3472

    1879

    Returns: 393393523

  12. 2084

    1211

    Returns: 332479778

  13. 3486

    3121

    Returns: 594104311

  14. 2429

    213

    Returns: 728538241

  15. 4499

    1945

    Returns: 30975948

  16. 1005

    746

    Returns: 634280269

  17. 2473

    1700

    Returns: 680424250

  18. 3205

    1183

    Returns: 67567882

  19. 4963

    3309

    Returns: 927321214

  20. 1132

    898

    Returns: 951390101

  21. 1652

    1332

    Returns: 308769331

  22. 866

    114

    Returns: 872442070

  23. 4056

    3673

    Returns: 142835969

  24. 1776

    1162

    Returns: 308226010

  25. 522

    278

    Returns: 301337086

  26. 1473

    1380

    Returns: 462192994

  27. 2317

    528

    Returns: 801556979

  28. 52

    26

    Returns: 946174989

  29. 4436

    440

    Returns: 213836018

  30. 4610

    3182

    Returns: 303331826

  31. 4516

    1630

    Returns: 31973048

  32. 2715

    578

    Returns: 757669177

  33. 1105

    700

    Returns: 733884475

  34. 4446

    1081

    Returns: 69966665

  35. 4266

    3228

    Returns: 886522289

  36. 4999

    2

    Returns: 880484492

  37. 5000

    3

    Returns: 536530413

  38. 2302

    1023

    Returns: 845254147

  39. 4993

    4987

    Returns: 756695992

  40. 5000

    7

    Returns: 820622157

  41. 10

    1

    Returns: 1000000000

  42. 100

    1

    Returns: 214240902

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: