Author: Sajal Sourav
Editorialist: Sajal Sourav
Combinatorics, Dynamic Programming
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 k1 groups of size x1, k2 groups of size x2, k3 groups of size x3 …
k1 * x1 + k2 * x2 + k3 * x3 … = N, and x1 != x2 != x3.
= N! / (x1!k1* k1! * x2!k2 * k2! * x3!k3 * k3! …)
Coming back to the original problem, we can see that
dp[i][j] = N! / (x1k1* k1! * x2k2 * k2! * x3k3 * k3! …)
such that k1 * x1 + k2 * x2 + k3 * x3 … = i, and x1 < x2 < x3 … < (j+1)
Refer to code for implementation details.
Author’s Solution can be found here