Advertisement
Guest User

Untitled

a guest
Jul 25th, 2016
2,606
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.11 KB | None | 0 0
  1. /*
  2. ID: hepic
  3. PROG: sabotage
  4. LANG: C++11
  5. */
  6. #include <bits/stdc++.h>
  7.  
  8. #define FOR(i, a, b) for(auto i=a; i<=b; ++i)
  9. #define REP(i, a, b) for(auto i=a; i<b; ++i)
  10. #define FORI(i, a, b) for(auto i=a; i!=b+1-2*(a>b); i+=1-2*(a>b))
  11. #define REPI(i, a, b) for(auto i=a-(a>b); i!=b-(a>b); i+=1-2*(a>b))
  12. #define ALL(v) v.begin(),v.end()
  13. #define mp(a, b) make_pair(a, b)
  14. #define pb(a) push_back(a)
  15. #define pf(a) push_front(a)
  16. #define eb(a, b) emplace_back(a, b)
  17. #define fir first
  18. #define sec second
  19. #define what_is(x) cout<<#x<<" is "<<x<<endl;
  20. #define type(x) typeid(x).name()
  21. #define ms(arr, val) memset(arr, val, sizeof(arr))
  22. #define min3(a,b,c) min(min(a,b),c)
  23. #define max3(a,b,c) max(max(a,b),c)
  24. #define SIZE 100010
  25. #define MAXN 1000000007LL
  26. #define NUM 1048576
  27. #define PI acos(-1)
  28. #define open_read1 freopen("a", "r", stdin)
  29. #define open_write1 freopen("b", "w", stdout)
  30. #define open_read freopen("poker.in", "r", stdin)
  31. #define open_write freopen("poker.out", "w", stdout)
  32.  
  33. using namespace std;
  34.  
  35. typedef long long LL;
  36. typedef long double LD;
  37. typedef unsigned long long ULL;
  38. typedef pair<double, double> PDD;
  39. typedef pair<int, int> PII;
  40. typedef pair<int, PII> PIPII;
  41. typedef pair<PII, PII> PPIIPII;
  42. typedef pair<LL, LL> PLL;
  43. typedef pair<ULL, ULL> PUU;
  44. typedef pair<LL, PLL> PLPLL;
  45. typedef pair<PLL, PLL> PPLLPLL;
  46.  
  47.  
  48. template<typename T, typename T1>
  49. ostream& operator << (ostream &out, pair<T, T1> obj)
  50. {
  51.     out<<"("<<obj.first<<","<<obj.second<<")";
  52.     return out;
  53. }
  54.  
  55.  
  56. template<typename T, typename T1>
  57. ostream& operator << (ostream &out, map<T, T1> cont)
  58. {
  59.     typename map<T, T1>::const_iterator itr = cont.begin();
  60.     typename map<T, T1>::const_iterator ends = cont.end();
  61.  
  62.     for(; itr!=ends; ++itr)
  63.         out<<*itr<<" ";
  64.     out<<endl;
  65.  
  66.     return out;
  67. }
  68.  
  69.  
  70. template<typename T>
  71. ostream& operator << (ostream &out, set<T> cont)
  72. {
  73.     typename set<T>::const_iterator itr = cont.begin();
  74.     typename set<T>::const_iterator ends = cont.end();
  75.  
  76.     for(; itr!=ends; ++itr)
  77.         out<<*itr<<" ";
  78.     out<<endl;
  79.  
  80.     return out;
  81. }
  82.  
  83.  
  84. template<typename T>
  85. ostream& operator << (ostream &out, multiset<T> cont)
  86. {
  87.     typename multiset<T>::const_iterator itr = cont.begin();
  88.     typename multiset<T>::const_iterator ends = cont.end();
  89.  
  90.     for(; itr!=ends; ++itr)
  91.         out<<*itr<<" ";
  92.     out<<endl;
  93.  
  94.     return out;
  95. }
  96.  
  97.  
  98. template<typename T, template<typename ELEM, typename ALLOC=allocator<ELEM>> class CONT>
  99. ostream& operator << (ostream &out, CONT<T> cont)
  100. {
  101.     typename CONT<T>::const_iterator itr = cont.begin();
  102.     typename CONT<T>::const_iterator ends = cont.end();
  103.  
  104.     for(; itr!=ends; ++itr)
  105.         out<<*itr<<" ";
  106.     out<<endl;
  107.  
  108.     return out;
  109. }
  110.  
  111.  
  112. template<typename T, unsigned int N, typename CTy, typename CTr>
  113. typename enable_if<!is_same<T, char>::value, basic_ostream<CTy, CTr> &>::type
  114. operator << (basic_ostream<CTy, CTr> &out, const T (&arr)[N])
  115. {
  116.      REP(i, 0, N)
  117.         out<<arr[i]<<" ";
  118.     out<<endl;
  119.  
  120.     return out;
  121. }
  122.  
  123.  
  124. template<typename T>
  125. T gcd(T a, T b)
  126. {
  127.     T min_v = min(a, b);
  128.     T max_v = max(a, b);
  129.  
  130.     while(min_v)
  131.     {
  132.         T temp = max_v % min_v;
  133.         max_v = min_v;
  134.         min_v = temp;
  135.     }
  136.  
  137.     return max_v;
  138. }
  139.  
  140.  
  141. template<typename T>
  142. T lcm(T a, T b)
  143. {
  144.     return (a*b) / gcd(a, b);
  145. }
  146.  
  147.  
  148. template<typename T>
  149. T fast_exp_pow(T base, T exp, T mod)
  150. {
  151.     LL res = 1;
  152.  
  153.     while(exp)
  154.     {
  155.         if(exp&1)
  156.         {
  157.             res *= base;
  158.             res %= mod;
  159.         }
  160.  
  161.         exp >>= 1;
  162.         base *= base;
  163.         base %= mod;
  164.     }
  165.  
  166.     return res;
  167. }
  168.  
  169. /*#################################################################################################################
  170. #################################################################################################################
  171. #################################################################################################################
  172. #################################################################################################################*/
  173.  
  174. int T, N;
  175. int exist[NUM];
  176. LL answer;
  177. LL numbers[SIZE], dp_solve[NUM+10][22];
  178.  
  179.  
  180.  
  181. int main()
  182. {
  183.     open_read1;
  184.     scanf("%d", &T);
  185.  
  186.     while(T--)
  187.     {
  188.         scanf("%d", &N);
  189.  
  190.         ms(exist, 0);
  191.         answer = 0;
  192.  
  193.         REP(i, 0, N)
  194.         {
  195.             scanf("%lld", numbers+i);
  196.             ++exist[numbers[i]];
  197.         }
  198.  
  199.         REP(i, 0, NUM)
  200.             dp_solve[i][0] = exist[i];
  201.  
  202.         FOR(i, 1, 20)
  203.         {
  204.             FOR(mask, 0, NUM)
  205.             {
  206.                 if(mask&(1<<(i-1)))
  207.                     dp_solve[mask][i] = dp_solve[mask^(1<<(i-1))][i-1];
  208.  
  209.                 else
  210.                 {
  211.                     dp_solve[mask][i] = dp_solve[mask][i-1];
  212.  
  213.                     if((mask^(1<<(i-1))) <= NUM)
  214.                         dp_solve[mask][i] += dp_solve[mask^(1<<(i-1))][i-1];
  215.                 }
  216.             }
  217.         }
  218.  
  219.         REP(i, 0, N)
  220.             answer += dp_solve[numbers[i]][20];
  221.  
  222.         if(exist[0])
  223.             --answer;
  224.  
  225.         printf("%lld\n", answer);
  226.     }
  227.  
  228.     return 0;
  229. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement