Advertisement
Guest User

Untitled

a guest
Aug 27th, 2015
488
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mp make_pair
  4. #define e1 first
  5. #define e2 second
  6. #define pb push_back
  7. typedef pair <int, int> PII;
  8. typedef unsigned int ui;
  9. typedef unsigned long long int ull;
  10. typedef long long int ll;
  11. typedef double ld;
  12. typedef pair <int, ll> PIL;
  13. typedef pair <ll, int> PLI;
  14. typedef pair <ll, ll> PLL;
  15. const int mod = 1e9+7;
  16. const int inf = 1e9+9;
  17. const ll MOD = 1e9+696969;
  18. const ll INF = ll(1e18) + 3;
  19. #define maxn 100100
  20. #define maxpot 18
  21. int n, a;
  22. int tab[maxn], pot[maxn], start[maxn];
  23. int dp[maxn];
  24. ll w;
  25. void moduluj(int &a)
  26. {
  27.     while (a >= mod) a -= mod;
  28. }
  29. inline int readint()
  30. {
  31.     int x = 0; char zn;
  32.     while (1)
  33.     {
  34.         zn = getchar();
  35.         if (isspace(zn)) return x;
  36.         x = (x << 1) + (x << 3) + zn - '0';
  37.     }
  38. }
  39. ll wyn[maxn];
  40.  
  41. int main()
  42. {
  43.     n = readint();
  44.     ll DUZO = mod;
  45.     DUZO *= DUZO;
  46.     pot[0] = 1;
  47.     int maks = 0;
  48.     for (int i=1; i<maxn; ++i) pot[i] = (pot[i-1] << 1), moduluj(pot[i]);
  49.  
  50.     for (int i=1; i<=n; ++i)
  51.     {
  52.         int a;
  53.         a = readint();
  54.         tab[a]++;
  55.         start[a]++;
  56.         maks = max(maks, a);
  57.     }
  58.     int P = 1, k = 0;
  59.     int bits[maxpot + 3];
  60.     while (P <= maks) P <<= 1, ++k;
  61.     ll wynall = 0;
  62.     for (int i=0; i<pot[k]; ++i)
  63.     {
  64.         int help = i; int DL= 0; int ile = __builtin_popcount(help);
  65.         for (int j=0; j<k; ++j)
  66.         {
  67.             if (help & 1) bits[++DL] = j;
  68.             help >>= 1;
  69.         }
  70.         int ILE = pot[DL] - 1;
  71.         for (int j=0; j<ILE; ++j)
  72.         {
  73.             int HELP = j, zbior = 0;
  74.             for (int zmienna = 1; zmienna <= DL; ++zmienna)
  75.             {
  76.                 if (HELP & 1) zbior |= pot[bits[zmienna]];
  77.                 HELP >>= 1;
  78.             }
  79.             tab[i] += start[zbior];
  80.             wyn[i] -= wyn[zbior];
  81.            
  82.         }
  83.  
  84.         wyn[i] += pot[tab[i]];
  85.         wyn[i] += DUZO;
  86.         wyn[i] %= mod;
  87.         ll w = i;
  88.         ll POMOC = w * w * w  % mod;
  89.         POMOC *= wyn[i];
  90.         wynall += POMOC;
  91.         wynall %= mod;
  92.     }
  93.  
  94.     cout << wynall;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement