fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const int mod = 1e9+7;
  5.  
  6. void fwt_or(vector<ll>& f, int sz) {
  7.     int m = f.size();
  8.     for(int b = 0; b < sz; b++){
  9.         for(int mask = 1; mask < m;  mask++){
  10.             if(mask & (1<<b)){
  11.                 f[mask] = (f[mask] + f[mask^(1<<b)]) % mod;
  12.             }
  13.         }
  14.     }
  15. }
  16.  
  17. void ifwt_or(vector<ll>& f, int sz){
  18.     int m = f.size();
  19.     for(int b = 0; b < sz; b++){
  20.         for(int mask = 1; mask < m;  mask++){
  21.             if(mask & (1<<b)){
  22.                 f[mask] = (f[mask] - f[mask^(1<<b)] + mod) % mod;
  23.             }
  24.         }
  25.     }
  26. }
  27.  
  28. int main(){
  29.     ios::sync_with_stdio(false);
  30.     cin.tie(nullptr);
  31.  
  32.     // freopen("SumOr.inp","r",stdin);
  33.     // freopen("SumOr.out","w",stdout);
  34.  
  35.     int n;
  36.     cin >> n;
  37.     vector<ll> a(n);
  38.     for(int i = 0; i < n; i++){
  39.         cin >> a[i];
  40.     }
  41.  
  42.     int sz = 0;
  43.     while((1<<sz) < n) sz++;
  44.     int m = 1<<sz;
  45.  
  46.     vector<ll> dp(m, 0);
  47.     for(int i = 0; i < n; i++){
  48.         dp[i] = a[i] % mod;
  49.     }
  50.  
  51.     fwt_or(dp, sz);
  52.  
  53.     for(int mask = 0; mask < m;  mask++){
  54.         dp[mask] = dp[mask] * dp[mask] % mod;
  55.     }
  56.  
  57.     ifwt_or(dp, sz);
  58. 	cout << dp[0] << " ";
  59.     for(int u = 1; u < n; u++){
  60.     	dp[u] = (dp[u] + dp[u - 1]) % mod;
  61.         cout << dp[u] << " ";
  62.     }
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5
2 3 5 5 3
stdout 
4 25 70 225 246
https://ideone.com/yPP4OJ
language:
C++14 (clang 8.0)
created:
6 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!