fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 1e9 + 7;
  5. using ll = long long;
  6.  
  7. int main() {
  8.     ios::sync_with_stdio(false);
  9.     cin.tie(nullptr);
  10.  
  11.     int n; 
  12.     if(!(cin >> n)) return 0;
  13.  
  14.     // Kích thước là power of two >= n
  15.     int M = 1;
  16.     while (M < n) M <<= 1;
  17.  
  18.     vector<ll> f(M, 0);
  19.     for (int i = 0; i < n; ++i) cin >> f[i];   // a[i] đặt ở chỉ số i (0-based)
  20.  
  21.     // FWT-OR (forward): F[mask] = sum_{submask ⊆ mask} a[submask]
  22.     for (int bit = 0; bit < __lg(M) + 1; ++bit) {
  23.         for (int mask = 0; mask < M; ++mask) if (mask & (1 << bit)) {
  24.             f[mask] = (f[mask] + f[mask ^ (1 << bit)]) % MOD;
  25.         }
  26.     }
  27.  
  28.     // Bình phương hệ số trong không gian FWT
  29.     for (int mask = 0; mask < M; ++mask) f[mask] = f[mask] * f[mask] % MOD;
  30.  
  31.     // FWT-OR (inverse): F[mask] = sum_{i|j=mask} a_i a_j  (OR-convolution)
  32.     for (int bit = 0; bit < __lg(M) + 1; ++bit) {
  33.         for (int mask = 0; mask < M; ++mask) if (mask & (1 << bit)) {
  34.             f[mask] = (f[mask] - f[mask ^ (1 << bit)]) % MOD;
  35.             if (f[mask] < 0) f[mask] += MOD;
  36.         }
  37.     }
  38.  
  39.     // Giờ f[mask] = h[mask] = sum_{i|j=mask} a_i a_j.
  40.     // Đáp án cho U là sum_{t ⊆ U} h[t]  → SOS DP theo submask:
  41.     for (int bit = 0; bit < __lg(M) + 1; ++bit) {
  42.         for (int mask = 0; mask < M; ++mask) if (mask & (1 << bit)) {
  43.             f[mask] += f[mask ^ (1 << bit)];
  44.             if (f[mask] >= MOD) f[mask] -= MOD;
  45.         }
  46.     }
  47.  
  48.     // In cho U = 0..n-1
  49.     for (int U = 0; U < n; ++U) {
  50.         cout << f[U] << (U + 1 == n ? '\n' : ' ');
  51.     }
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3
1 2 8
stdout
copy 
1 9 81
https://ideone.com/MycHmP
language:
C++14 (gcc 8.3)
created:
11 hours 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!