Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
2.3 kB
8
Indexable
#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))
#define Task "andsum"

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")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }

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

    // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
    // cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}
Leave a Comment