PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
Inclusion Exclusion can be used to solve the problem. Let F(i,j) denote the number of ways in which atleast a given set of i people who do not purchase anything and
atleast a given set of j items which are not purchased by anyone.
F(i,j) = ncr[(n - i) * (m - j)][r] ;
There are ncr[n][i] ways to choose i people from n people, and ncr[m][j] ways to choose j items from m items. Let
G(i,j) = ncr[n][i] * ncr[m][j] * F(i,j)
The final answer is given by summing G(i,j) over all (i,j). We add G(i,j) to the answer if (i + j) is even, else we subtract it.