Guest User

Untitled

a guest
Jul 25th, 2016
1,027
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×