登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4289
  • 题目
  • P4289Too Young
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 3s

    When nidgd was young, he used to play with boxes and balls. In his mind, a large quantity of boxes was as magical as constellations in the sky, and each ball in box was identical to a star which belongs to the constellation. One day nidgd made a statistic. There were 𝒏 boxes and 𝒎 kinds of balls. Each box contained some different kinds of balls. One kind of balls could appear in multiple boxes. Empty boxes were accepted. The next day, nidgd wanted to go on a journey, and wanted to take every kind of balls. Distinctly, he needed to take at least one ball of each type. However, nidgd has some psychosis that if he is going to bring some balls, he would bring all the balls in the boxes together. So he could only take some boxes of balls to cover all types, despite that there might be some repetition. Then nidgd want to know: how many different plans of choosing boxes satisfied the condition? The answer might be very great, so please modulo 10^9 + 7.


    Input file is The first line of input contains two integers 𝒏 and 𝒎, the number of boxes and the number of ball types. Following that there are 𝒏 lines, each line describe a box. At the beginning of the 𝒊 𝒕𝒕 line is a integer 𝒌𝒊, the number of ball in the 𝒊th box. Then 𝒌𝒊 integers 𝒄𝒊𝒊, 𝒄𝒊𝒊, … 𝒄𝒊𝒌𝒊 , describe types of balls.


    Output file is A.out. Print a single integer as the answer modulo 10^9 + 7.


    3 3
    3 1 2 3
    3 1 2 3
    3 1 2 3




    【Hint】 There are 3 boxes and 3 kinds of balls. Each box contains all kinds of balls. Each box can be chosen or not independently but it must choose at least one box. So we have 7 different plans.

    【Data Range】 There are 20% of test cases, 𝑛 ≤ 20, 𝑚 ≤ 16. There are 40% of test cases, 𝑛 ≤ 103, 𝑚 ≤ 16. There are 70% of test cases, 𝑛 ≤ 106, 𝑚 ≤ 16. All 100% of test cases, 𝑛 ≤ 106, 𝑚 ≤ 22, 0 ≤ 𝑘𝑖 ≤ 𝑚, 1 ≤ 𝑐𝑖𝑖 ≤ 𝑚.

    【Warning】 Huge input, scanf is too slow!

    来源  nodgd