fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main(){
  6. 	// freopen("SumOverSubset.inp", "r", stdin);
  7. 	// freopen("SumOverSubset.out", "w", stdout);
  8.     ios_base::sync_with_stdio(false);
  9.     cin.tie(NULL);
  10.     int n, x; cin >> n;
  11.     long long mx = 0;
  12.     const int mod = 1e9 + 7;
  13.     long long dp2[n + 5], dp[n + 5], a[n + 5];
  14.     bool chk[n + 5];
  15.     memset(dp, 0, sizeof dp);
  16.     memset(dp2, 0, sizeof dp2);
  17.     memset(chk, 0, sizeof chk);
  18.     for(int i = 0; i < n; i++){
  19.     	cin >> a[i];
  20.     	mx = max(mx, a[i]);
  21.     	dp[i] = a[i];
  22.     	dp2[i] = a[i] * a[i];
  23.     }
  24.     int sz = floor(log2(mx)) + 1;
  25.     for(int i = 0; i < sz; i++){
  26.     	for(int j = 1; j < n; j++){
  27.     		if((j >> i) & 1){
  28.     			dp[j] += dp[j ^ (1 << i)];
  29.     		}
  30.     	}
  31.     }
  32.     dp[0] = dp[0] * dp[0];
  33.     for(int i = 1; i < n; i++){
  34.     	dp[i] = dp[i] * dp[i];
  35.     	//dp[i] += dp[i - 1];
  36.     }
  37.     // for(int i = 0; i < n; i++){
  38.     // 	cout << dp[i] << " ";
  39.     // }
  40.     for(int i = 0; i < sz; i++){
  41.     	for(int j = 1; j < n; j++){
  42.     		if((j >> i) & 1){
  43.     			dp[j] -= dp[j ^ (1 << i)];
  44.     		}
  45.     	}
  46.     }
  47.     cout << dp[0] << " ";
  48.     for(int i = 1; i < n; i++){
  49.     	dp[i] += dp[i - 1];
  50.     	cout << dp[i] << " ";
  51.     }
  52.  
  53.  
  54.  
  55.     return 0;
  56.  
  57. }
  58.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
5
2 3 5 5 3
stdout
copy 
4 25 70 225 246
https://ideone.com/R66bGd
language:
C++14 (clang 8.0)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!