Untitled
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