CrazyFunctions | Topcoder Archive

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

```
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
```
```
Returns: 2
```
```
1
```
```
1
```
```
Returns: 1
```
```
3
```
```
1
```
```
Returns: 9
```
```
3
```
```
3
```
```
Returns: 6
```
```
5
```
```
3
```
```
Returns: 900
```
```
5000
```
```
5000
```
```
Returns: 541108809
```

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.