Advertisement
Guest User

GoodSubset

a guest
Sep 5th, 2014
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <deque>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <ctime>
  20.  
  21. #define MOD 1000000007
  22.  
  23. using namespace std;
  24.  
  25.  
  26. class GoodSubset {
  27. public:
  28.   int numberOfSubsets(int goodValue, vector <int> d) {
  29.     map<long long, long long> buffer;
  30.     map<long long, long long>::iterator it;
  31.     for(int j=0;j<d.size();j++)
  32.         {
  33.             vector<pair<long long, long long> > toadd;
  34.             if (goodValue % d[j] == 0) toadd.push_back(make_pair(d[j],1));
  35.             for(it=buffer.begin();it!=buffer.end();it++)
  36.                 if(goodValue % (it->first * d[j]) == 0)
  37.                     toadd.push_back(make_pair(it->first*d[j],it->second));
  38.             for(int k=0;k<toadd.size();k++)
  39.             {
  40.                 buffer[toadd[k].first]=(buffer[toadd[k].first]+toadd[k].second)%MOD;
  41.             }
  42.         }
  43.         return buffer[goodValue];
  44.   }
  45. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement