**Author:** Sajal Sourav

**Editorialist:** Sajal Sourav

## DIFFICULTY:

Medium

## PREREQUISITES:

Combinatorics, Dynamic Programming

## EXPLANATION:

Make a graph of **N** vertices. For every i (from 1 to **N**), add an edge from i to f(i).

The above graph will consist of cycles.

- For any cycle of even length number of ways to color it will be M*M.
- For odd length number of ways to color it will be M.

To find the total number of functions(f), we have to divide **N** vertices into cycles,

- for odd Cycles answer will be multiplied by
**M**and - for even Cycles answer will be multiplied by
**M*M**.

This can be solved by Dynamic Programming

**dp[i][j]** - number of ways to divide i elements into Cycles of size less equal to j.

Now consider this subproblem,

We have **N** items and we have to divide it into **k _{1}** groups of size

**x**,

_{1}**k**groups of size

_{2}**x**,

_{2}**k**groups of size

_{3}**x**…

_{3}**k***

_{1}**x**+

_{1}**k***

_{2}**x**+

_{2}**k***

_{3}**x**… =

_{3}**N**, and

**x**!=

_{1}**x**!=

_{2}**x**.

_{3}= **N!** / (**x _{1}!**

^{k1}*

**k***

_{1}!**x**

_{2}!^{k2}*

**k***

_{2}!**x**

_{3}!^{k3}*

**k**…)

_{3}!Coming back to the original problem, we can see that

**dp[i][j]** = **N!** / (**x _{1}**

^{k1}*

**k***

_{1}!**x**

_{2}^{k2}*

**k***

_{2}!**x**

_{3}^{k3}*

**k**…)

_{3}!such that **k _{1}** *

**x**+

_{1}**k***

_{2}**x**+

_{2}**k***

_{3}**x**… =

_{3}**i**, and

**x**<

_{1}**x**<

_{2}**x**… <

_{3}**(j+1)**

Refer to code for implementation details.

Author’s Solution can be found here