# Untitled

unknown
plain_text
a month ago
2.3 kB
7
Indexable
Never
```#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define vi vector<int>
#define bit(i, x) ((x >> i) & 1)
#define ALL(x) x.begin(), x.end()
#define REP(i, n) for (int i = 1; i <= n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORD(i, a, b) for (int i = a; i >= b; --i)
#define Random(lf, rt) (lf + rand() % (rt - lf + 1))

using namespace std;
const int maxn = 1e6 + 7, N = 1e9 + 7, mod = 1e9 + 7;

void ADD(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
if (x < 0) x += mod;
}
void MAXIMIZE(int &x, int y) {
x = max(x, y);
}
void MINIMIZE(int &x, int y) {
x = min(x, y);
}

int n;
int a[maxn], f[maxn];

void sub1_1() {
//for n^2
REP(i, n) {
f[i] = 0;
REP(j, n) if ((i & j) == j)
f[i] += a[j];
}
REP(i, n) cout << f[i] << " \n"[i == n];
}

void sub1_2() {
//n^2 cai tien
REP(i, n) {
f[i] = 0;
for (int j = i; j; j = (j - 1) & i)
f[i] += a[j];
}
REP(i, n) cout << f[i] << " \n"[i == n];
}

int dp[maxn][23];
void sub2_1() {
//dp 2 chieu
int LOG = log2(n) + 1;
REP(i, n) {
dp[i][0] = a[i];
REP(j, LOG) {
if (bit(j - 1, i))
dp[i][j] = dp[i][j - 1] + dp[i ^ (1 << (j - 1))][j - 1];
else dp[i][j] = dp[i][j - 1];
}
}
REP(i, n) cout << dp[i][LOG] << " \n"[i == n];
}

void sub2_2() {
//dp 1 chieu
int LOG = log2(n) + 1;
REP(i, n) f[i] = a[i];
REP(j, LOG) REP(i, n) if (bit(j - 1, i))
f[i] += f[i ^ (1 << (j - 1))];
REP(i, n) cout << f[i] << " \n"[i == n];
}

signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(Task".inp", "r")) {
}

cin >> n;
REP(i, n) cin >> a[i];
// sub1_1();
// sub1_2();
// sub2_1();
sub2_2();