[Solved]: Number of ways to fill a 2xN grid with M colors

Problem Detail: 

This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri. In short, the question asked to find the number of ways to fill a $ 2\times N$ grid with $M$ colors such that no two cells with the same row or same column have the same color.

The limits given are $1 \leq N$, and $M \leq 1000$ with 1000 test cases per input.

Based on the constraints the approach that comes to my mind after a long struggle includes having a precomputed DP table which can be used for every test case. I tried to apply the inclusion-exclusion principle but could not come up with any solution. I also tried to solve it using bipartite perfect matchings, but no success. How should I approach this question?

Asked By : Kyuubi

Answered By : Yuval Filmus

You can use inclusion-exclusion. There are $M!/(M-N)!$ choices for the first row. Fix these choices. The number of choices for the second row in which $T$ specific columns are bad (but the row itself is good) is $(M-T)!/(M-N)!$. According to the inclusion-exclusion principle, the required number is $$ \frac{M!}{(M-N)!} \sum_{T=0}^N (-1)^T \binom{N}{T} \frac{(M-T)!}{(M-N)!}. $$ I'll let you take it from here.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19288