# Untitled

a guest
Jun 20th, 2017
69
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*************
2.         Author - am10
3.              ******************/
4. #include<bits/stdc++.h>
5.
6. #define sync ios::sync_with_stdio(false)
7. #define endl '\n'
8. #define ll long long
9. #define pb push_back
10. #define PI acos(-1)
11. #define pii pair <int,int>
12. #define FI first
13. #define SE second
14. #define MOD 1000000007
15. /*
16. //D-S-U
17. int root(int v){return par[v] < 0 ? v : (par[v] = root(par[v]));}
18. void merge(int x,int y){    //  x and y are some tools (vertices)
19.         if((x = root(x)) == (y = root(y))     return ;
20.     if(par[y] < par[x]) // balancing the height of the tree
21.         swap(x, y);
22.     par[x] += par[y];
23.     par[y] = x;
24. }
25. */
26.
27. //**********MODULAR EXPONENTIATION******************/
28.
29.
30. using namespace std;
31.
32. vector <vector<int> > v(1000006);
33. int n,m;
34.
35. int power(int x, int y)
36. {
37.     int res = 1;      // Initialize result
38.     ll  p = MOD;
39.     x = x % p;  // Update x if it is more than or
40.                 // equal to p
41.
42.     while (y > 0)
43.     {
44.         // If y is odd, multiply x with result
45.         if (y & 1)
46.             res = (res*x) % p;
47.
48.         // y must be even now
49.         y = y>>1; // y = y/2
50.         x = (x*x) % p;
51.     }
52.     return res%p;
53. }
54. //parameter box index and set which stores unique element till now of chosen box
55. int solve(int start,set<int> s)
56. {
57.    if(start>=n)
58.   {
59.     return 0;
60.   }
61.   set <int> p = s;
62.   //if size of set == m then we can include or exclude remaining so ans is 2^remaining
63.   if(s.size() == m)
64.   {
65.     return power(2,n-1-start);
66.   }
67.   else
68.   {
69.      //include start+1 box
70.      for(int i=0;i<v[start].size();i++)
71.         s.insert(v[start][i]);
72.      int ans1 = solve(start+1,s)%MOD;
73.      //exclude start+1 box
74.      int ans2 =  solve(start+2,p)%MOD;
75.      return (ans1%MOD + ans2%MOD)%MOD;
76.   }
77. }
78.
79. int main()
80. {
81.   sync;
82.   cin >> n >> m;
83.   for(int i=0;i<n;i++)
84.   {
85.     int k;
86.     cin >> k;
87.     for(int j=0;j<k;j++)
88.     {
89.       int x;
90.       cin >> x;
91.       v[i].pb(x);
92.     }
93.   }
94.   int res = 0;
95.   set <int> s;
96.   //Checking for each subset in which ith box is fixed
97.   for(int i=0;i<n;i++)
98.   {
99.     for(int k=0;k<m;k++)
100.       s.insert(v[i][k]);
101.     res = (res%MOD + solve(i,s)%MOD)%MOD;
102.     s.clear();
103.   }
104.   cout << res%MOD << endl;
105. }
RAW Paste Data