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?
Number of ways to fill a 2xN grid with M colors
graph theory;combinatorics;permutations;bipartite matching
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.