Untitled

unknown
c_cpp
14 days ago
2.3 kB
7
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tt, tc;

const int mod = 1e9 + 7;
int add(int x, int y) { return (x + y) % mod; }
int sub(int x, int y) { return (x - y + mod) % mod; }
int mul(int x, int y) { return (x * 1LL * y) % mod; }
int modpow(int n, int k) {
int res = 1;
while (k) {
if (k & 1) res = mul(res, n);
n = mul(n, n);
k >>= 1;
}
return res;
}
int divide(int a, int b) { return mul(a, modpow(b, mod - 2)); }

struct fenwick_point {
int n;
vector<int> fenw;
fenwick_point(int _n) : n(_n + 5) { fenw.resize(n); }

void increment(int i, int v) {
for (++i; i < n; i += (i & -i)) fenw[i] = add(fenw[i], v);
}
int query(int i) {
int res = 0;
for (++i; i > 0; i -= (i & -i)) res = add(res, fenw[i]);
return res;
}
};

void solve() {
int n;
cin >> n;
vector<ll> a(n);
for (ll& u : a) cin >> u;

auto modulo = [&](ll x) {
while (x < 0) x += (ll)mod;
return x % mod;
};

map<ll, int> comp;
for (ll u : a) comp[u];
int id = 1;
for (auto& u : comp) u.second = id++;

fenwick_point freq(n + 1);
fenwick_point sum(n + 5);

vector<int> p2(n + 5), invp2(n + 5);
p2[0] = invp2[0] = 1;
p2[1] = 2;
invp2[1] = divide(1, 2);
for (int i = 2; i <= n + 4; i++) {
p2[i] = mul(p2[i - 1], p2[1]);
invp2[i] = mul(invp2[i - 1], invp2[1]);
}

int res = 0;
for (int i = 0; i < n; i++) {
int j = comp[a[i]];

// (a[i] - a[before]) * 2^{before - 1} * 2^{n - i - 1}
res = add(res, mul(mul(modulo(a[i]), freq.query(j - 1)), p2[n - i - 1]));
res = sub(res, mul(sum.query(j - 1), p2[n - i - 1]));

// (a[before] - a[i]) * 2^{before - 1} * 2^{n - i - 1}
res = add(res, mul(sub(sum.query(n + 3), sum.query(j - 1)), p2[n - i - 1]));
res = sub(res, mul(mul(modulo(a[i]), p2[n - i - 1]), sub(freq.query(n + 3), freq.query(j - 1))));

freq.increment(j, p2[i]);
sum.increment(j, mul(p2[i], modulo(a[i])));
}

cout << res << "\n";
}

int main() {
ios::sync_with_stdio(0); cin.tie(0);
tt = 1, tc = 1; // cin >> tt;
while (tt--) solve(), tc++;
}```