Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define mp make_pair
- #define e1 first
- #define e2 second
- #define pb push_back
- typedef pair <int, int> PII;
- typedef unsigned int ui;
- typedef unsigned long long int ull;
- typedef long long int ll;
- typedef double ld;
- typedef pair <int, ll> PIL;
- typedef pair <ll, int> PLI;
- typedef pair <ll, ll> PLL;
- const int mod = 1e9+7;
- const int inf = 1e9+9;
- const ll MOD = 1e9+696969;
- const ll INF = ll(1e18) + 3;
- #define maxn 100100
- #define maxpot 18
- int n, a;
- int tab[maxn], pot[maxn], start[maxn];
- int dp[maxn];
- ll w;
- void moduluj(int &a)
- {
- while (a >= mod) a -= mod;
- }
- inline int readint()
- {
- int x = 0; char zn;
- while (1)
- {
- zn = getchar();
- if (isspace(zn)) return x;
- x = (x << 1) + (x << 3) + zn - '0';
- }
- }
- ll wyn[maxn];
- int main()
- {
- n = readint();
- ll DUZO = mod;
- DUZO *= DUZO;
- pot[0] = 1;
- int maks = 0;
- for (int i=1; i<maxn; ++i) pot[i] = (pot[i-1] << 1), moduluj(pot[i]);
- for (int i=1; i<=n; ++i)
- {
- int a;
- a = readint();
- tab[a]++;
- start[a]++;
- maks = max(maks, a);
- }
- int P = 1, k = 0;
- int bits[maxpot + 3];
- while (P <= maks) P <<= 1, ++k;
- ll wynall = 0;
- for (int i=0; i<pot[k]; ++i)
- {
- int help = i; int DL= 0; int ile = __builtin_popcount(help);
- for (int j=0; j<k; ++j)
- {
- if (help & 1) bits[++DL] = j;
- help >>= 1;
- }
- int ILE = pot[DL] - 1;
- for (int j=0; j<ILE; ++j)
- {
- int HELP = j, zbior = 0;
- for (int zmienna = 1; zmienna <= DL; ++zmienna)
- {
- if (HELP & 1) zbior |= pot[bits[zmienna]];
- HELP >>= 1;
- }
- tab[i] += start[zbior];
- wyn[i] -= wyn[zbior];
- }
- wyn[i] += pot[tab[i]];
- wyn[i] += DUZO;
- wyn[i] %= mod;
- ll w = i;
- ll POMOC = w * w * w % mod;
- POMOC *= wyn[i];
- wynall += POMOC;
- wynall %= mod;
- }
- cout << wynall;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement