Guest User

Untitled

a guest
Jun 20th, 2017
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.19 KB | None | 0 0
  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. }
Add Comment
Please, Sign In to add comment