FUNFUN - Editorial

general
, , , ,
1

Links
Contest
Practice

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.

  1. For any cycle of even length number of ways to color it will be M*M.
  2. 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,

  1. for odd Cycles answer will be multiplied by M and
  2. 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

1 Like
2

please provide a complete editorial, how dp[i][j] is going to help us to get to the final answer.