# PROBLEM LINKS

Practice

Contest

# 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.

asked
**28 Nov '12, 19:40**

0★admin ♦♦

19.8k●350●498●541

accept rate:
36%