Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.5 kB
0
Indexable
Never
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = (1 << 19);
const int MOD = 1000000007;

int n;
int arr[MAX_N];
int sum[MAX_N];
int dp[MAX_N];

int getBit(int num, int pos) {
    return (num >> pos) & 1;
}

void add(int &a, int b) {
    a += b;
    if (a >= MOD) {
        a -= MOD;
    }
}

void sub(int &a, int b) {
    a -= b;
    if (a < 0) {
        a += MOD;
    }
}

void addSOS(int dp[], int n = 19) {
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < MAX_N; mask++) {
            if (getBit(mask, i)) {
                add(dp[mask], dp[mask ^ (1 << i)]);
            }
        }
    }
}

void subSOS(int dp[], int n = 19) {
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < MAX_N; mask++) {
            if (getBit(mask, i)) {
                sub(dp[mask], dp[mask ^ (1 << i)]);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("orsum.inp", "r")) {
        freopen("orsum.inp", "r", stdin);
        freopen("orsum.out", "w", stdout);
    }

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        sum[i] = arr[i];
    }

    addSOS(sum);
    for (int i = 0; i < MAX_N; i++) {
        dp[i] = (long long)sum[i] * sum[i] % MOD;
    }
    subSOS(dp);
    for (int i = 1; i < n; i++) {
        add(dp[i], dp[i - 1]);
    }

    for (int i = 0; i < n; i++) {
        cout << dp[i] << " ";
    }

    return 0;
}
Leave a Comment