Solution of Zombie

The problem requires you to count the number of surjections defined on a domain of cardinal N and codomain of cardinal M and multiply it by the number of derangements of M.

In order to count this we use Inclusion-Exclusion Principle in the following way:
Sum(K <- 0, M) (M choose K) * (M - K) ^ N * (-1) ^ K. We basically choose out of the M elements of the codomain, which of them we don't map anything to and then map the N elements of the domain in all the possible ways to the remainig (M - K) elements of the codomain. To count the number of derangements we can use again the principle of inclusion and exclusion. N! - AtLeastOneElementMappedCorrectly is the number of derangements. To count the number of ways we can map at least 1 element correctly, we use IEP in the following way: Sum(K <- 1, M) (M choose K) * (M - K)!. We basically choose at any step K out of the M elements to be mapped correctly and permute the remaining (M - K) elements. Complexity: O(M + M log MOD) = O(M)

Questions?

Sponsors Gold