Advertisement
Guest User

Kosare

a guest
Apr 15th, 2012
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #include <algorithm>
  3. #include <string>
  4. #include <set>
  5. #include <map>
  6. #include <vector>
  7. #include <queue>
  8. #include <iostream>
  9. #include <iterator>
  10. #include <cmath>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <sstream>
  14. #include <fstream>
  15. #include <ctime>
  16. #include <cstring>
  17. #pragma comment(linker, "/STACK:66777216")
  18. using namespace std;
  19. #define pb push_back
  20. #define ppb pop_back
  21. #define pi 3.1415926535897932384626433832795028841971
  22. #define mp make_pair
  23. #define x first
  24. #define y second
  25. #define pii pair<int,int>
  26. #define pdd pair<double,double>
  27. #define INF 1000000000
  28. #define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
  29. #define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
  30. #define all(c) (c).begin(), (c).end()
  31. #define SORT(c) sort(all(c))
  32. #define rep(i,n) FOR(i,1,(n))
  33. #define rept(i,n) FOR(i,0,(n)-1)
  34. #define L(s) (int)((s).size())
  35. #define C(a) memset((a),0,sizeof(a))
  36. #define VI vector <int>
  37. #define ll long long
  38. #define MOD 1000000007
  39.  
  40. int a,b,c,d,i,j,n,m,k;
  41. int g[1 << 20], p2[1 << 20];
  42. int main() {
  43. //  freopen("input.txt","r",stdin);
  44. //  freopen("output.txt","w",stdout);
  45.    
  46.     scanf("%d%d", &n, &m);
  47.     rept(i, n) {
  48.         scanf("%d", &b);
  49.         c = 0;
  50.         rept(j, b) {
  51.             scanf("%d", &a);
  52.             c |= 1 << (a - 1);
  53.         }
  54.         ++g[c];
  55.     }
  56.  
  57.     rept(i, m)
  58.         rept(mask, 1 << m)
  59.             if (mask & 1 << i) g[mask] += g[mask ^ 1 << i];
  60.  
  61.     p2[0] = 1;
  62.     rep(i, n) {
  63.         p2[i] = p2[i - 1] * 2;
  64.         if (p2[i] >= MOD) p2[i] -= MOD;
  65.     }
  66.  
  67.     int ans = 0;
  68.     rept(mask, 1 << m) {
  69.         c = 0;
  70.         rept(i, m) if (mask & 1 << i) ++c;
  71.         if ((m + c) % 2) ans -= p2[g[mask]]; else
  72.         ans += p2[g[mask]];
  73.         if (ans < 0) ans += MOD;
  74.         if (ans >= MOD) ans -= MOD;
  75.     }
  76.     printf("%d\n", ans);
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement