시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 107 | 89 | 77 | 82.796% |
Oh how the cows love their pizza! Even though they are picky, they do love variety, too. They order from the local pizza parlor that features T (1 <= T <= 20) different toppings in addition to a complete set of soft drinks and healthy salads.
The toppings are conveniently numbered 1..T so the cows can order by number. Your job is to calculate how many possible pizzas can be created given that some cows will not tolerate various combinations of toppings (e.g., some cows simply will not eat Anchovies or the combination of Mushrooms and Asparagus).
Given a set of N (1 <= N <= 52) constraints, figure out how many pizzas can be made using all possible combinations of the ingredients (which, of course, includes no ingredients at all). Each constraint is a set of numbers of size 1..T that lists the ingredients that disqualify a pizza from being considered.
A constraint like "5 3" means that no pizza can contain ingredient #5 and also ingredient #3. This means a pizza with ingredients 3, 5, and 6 will not be counted as acceptable.
6 5 1 1 2 4 2 3 3 2 6 1 5 3 3 4 6
10