fork download
copy 
  1. import sys
  2.  
  3. def main():
  4.     mod = 1000000007
  5.     data = sys.stdin.buffer.read().split()
  6.     it = iter(data)
  7.     N = int(next(it))
  8.     M = int(next(it))
  9.     size = 1 << M
  10.  
  11.     dp = [0] * size
  12.     for _ in range(N):
  13.         k = int(next(it))
  14.         mask = 0
  15.         for _ in range(k):
  16.             t = int(next(it))
  17.             mask |= 1 << (t - 1)
  18.         dp[mask] += 1
  19.  
  20.     f = dp[:]
  21.  
  22.     for i in range(M):
  23.         bit = 1 << i
  24.         step = bit << 1
  25.         for base in range(0, size, step):
  26.             mid = base + bit
  27.             end = base + step
  28.             if end > size:
  29.                 end = size
  30.             for j in range(mid, end):
  31.                 f[j] += f[j - bit]
  32.  
  33.     full = size - 1
  34.     res = 0
  35.     for S in range(size):
  36.         if (S.bit_count() & 1) == 0:
  37.             sign = 1
  38.         else:
  39.             sign = -1
  40.         exp = f[full ^ S]
  41.         res = (res + sign * pow(2, exp, mod)) % mod
  42.     sys.stdout.write(str(res % mod))
  43.  
  44. if __name__ == '__main__':
  45.     main()
  46.  
Success #stdin #stdout 0.09s 14100KB
comments (?)
stdin
copy 
3 3
3 1 2 3
3 1 2 3
3 1 2 3
stdout
copy 
7
https://ideone.com/sfivqD
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!