fork download
copy 
  1. #include <bits/stdc++.h>  //i'm falling in love with you 💞
  2.  
  3. using namespace std;
  4. #define MOD ll(1e9+7)
  5. #define N 1000006
  6. #define MASK (1<<20)
  7. typedef long long ll;
  8.  
  9. ll dp[MASK],pow_2[N];
  10.  
  11. int main()
  12. {
  13.     ios_base::sync_with_stdio(NULL);
  14.     cin.tie(NULL);
  15.  
  16.     #ifndef ONLINE_JUDGE
  17.     freopen("input.inp","r",stdin);
  18.     freopen("output.out","w",stdout);
  19.     #endif 
  20.  
  21.     int n, m; cin >> n >> m;
  22.  
  23.     for (int i = 1; i <= n; i++) 
  24.     {
  25.         int k; cin >> k;
  26.         int mask = 0;
  27.         for (int j = 1; j <= k; j++)
  28.         {
  29.             int x; cin >> x;
  30.             mask += (1 << (x - 1));
  31.         }
  32.  
  33.         dp[mask]++;
  34.     }
  35.  
  36.     pow_2[0] = 1;
  37.     for (ll i = 1;  i <= n; i++) pow_2[i] = pow_2[i - 1] * 2 % MOD;
  38.  
  39.     for (int i = 0; i < m; i++) 
  40.         for (int mask = 0; mask < (1 << m); mask++)
  41.             if ((mask >> i) & 1) dp[mask] += dp[mask ^ (1 << i)];
  42.  
  43.     ll ans = 0;
  44.     for (int mask = 0; mask < (1 << m); mask++)
  45.         if (__builtin_popcount(mask) % 2 == m % 2) 
  46.             ans = (ans + pow_2[dp[mask]] - 1 + MOD) % MOD;
  47.         else 
  48.             ans = (ans - pow_2[dp[mask]] + 1 + MOD) % MOD;
  49.  
  50.     cout << ans ;
  51.  
  52.  
  53.  
  54. }
Success #stdin #stdout 0s 5648KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/8X3f7f
language:
C++14 (gcc 8.3)
created:
6 days 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!