fork download
copy 
  1. #include <bits/stdc++.h>
  2. // Useful stuff
  3. template<int mod>
  4. struct IntMod {
  5.     int value;
  6.     IntMod(int value_ = 0) : value(value_) { }
  7.     IntMod& operator+=(IntMod num) {
  8.         value += num.value;
  9.         if (value >= mod) value -= mod;
  10.         return *this;
  11.     }
  12.     IntMod& operator-=(IntMod num) {
  13.         value -= num.value;
  14.         if (value < 0) value += mod;
  15.         return *this;
  16.     }
  17.     IntMod operator*(IntMod num) const { return IntMod(int(1LL * value * num.value % mod)); }
  18.     IntMod operator+(IntMod num) const { return IntMod(*this) += num; }
  19.     IntMod operator-(IntMod num) const { return IntMod(*this) -= num; }
  20.     IntMod& operator*=(IntMod num) { return *this = *this * num; }
  21. };
  22. template<typename T>
  23. T pow(T a, int n) {
  24.     T r(1);
  25.     while (n > 0) {
  26.         if (n & 1) {
  27.             r *= a;
  28.         }
  29.         a *= a;
  30.         n >>= 1;
  31.     }
  32.     return r;
  33. }
  34. const int mod = (int)1e9+7;
  35. using Int = IntMod<mod>;
  36.  
  37. int main() {
  38.     std::ios_base::sync_with_stdio(false);
  39.     std::cin.tie(0);
  40.     // Input:
  41.     int n; std::cin >> n;
  42.     std::vector<int> arr(n);
  43.     for (auto &it : arr) {
  44.         std::cin >> it;
  45.         it = ~it & ((1 << 20) - 1); // inverting
  46.     }
  47.     // Counting numbers:
  48.     std::vector<int> cnt(1 << 20);
  49.     for (auto it : arr) {
  50.         cnt[it]++;
  51.     }
  52.     // DP over subsets:
  53.     auto dp = cnt;
  54.     for (int bit = 0; bit < 20; bit++) {
  55.         for (int mask = 0; mask < (1 << 20); mask++) {
  56.             if ((mask >> bit) & 1) {
  57.                 dp[mask] += dp[mask ^ (1 << bit)];
  58.             }
  59.         }
  60.     }
  61.     // Calculating answer:
  62.     Int answ(1); // empty subset is correct
  63.     for (int mask = 0; mask < (1 << 20); mask++) {
  64.         // Every item, greater, than current, can be included or not: 2^cntGreater ways
  65.         auto fi = pow(Int(2), dp[mask] - cnt[mask]);
  66.         // At least 1 item, equal to `mask`, should be included: 2^cnt-1 ways
  67.         // Add a multiplication to answer
  68.         auto se = pow(Int(2), cnt[mask]) - 1;
  69.         answ += fi * se;
  70.     }
  71.     // Getting answer for given problem:
  72.     answ = pow(Int(2), n) - answ;
  73.     std::cout << answ.value << std::endl;
  74.     return 0;
  75. }
Success #stdin #stdout 0.02s 11264KB
comments (?)
stdin
copy 
5
0 2 5 3 7
stdout
copy 
6
https://ideone.com/203YJs
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!