fork download
copy 
  1. #pragma GCC optimize("O3,unroll-loops")
  2. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. const unsigned int MOD = 998244353;
  8.  
  9. // Đưa về mảng 1 chiều x 24 để tận dụng thanh ghi AVX2 (256-bit = 8 số int x 3)
  10. // Đảo chiều mảng thành f[mask][k] để tối ưu Cache locality
  11. alignas(32) unsigned int f[1 << 20][24]; 
  12.  
  13. int main() {
  14.     ios_base::sync_with_stdio(false);
  15.     cin.tie(NULL);
  16.  
  17.     freopen("tamphan.inp" , "r" , stdin);
  18.     freopen("tamphan.out" , "w" , stdout);
  19.  
  20.     int n;
  21.     if (!(cin >> n)) return 0;
  22.  
  23.     int size = 1 << n;
  24.     for (int i = 0; i < size; ++i) {
  25.         unsigned int val;
  26.         cin >> val;
  27.         f[i][__builtin_popcount(i)] = val;
  28.     }
  29.  
  30.     // 1. FMT / SOS DP
  31.     for (int len = 1; len < size; len <<= 1) {
  32.         for (int i = 0; i < size; i += 2 * len) {
  33.             for (int j = 0; j < len; ++j) {
  34.                 unsigned int *u = f[i + j];
  35.                 unsigned int *v = f[i + len + j];
  36.                 for (int k = 0; k <= n; ++k) {
  37.                     unsigned int sum = v[k] + u[k];
  38.                     // Phép cộng không nhánh (branchless) thay cho modulo
  39.                     v[k] = (sum >= MOD) ? sum - MOD : sum;
  40.                 }
  41.             }
  42.         }
  43.     }
  44.  
  45.     // 2. Nhân chập đa thức (Tính trực tiếp không cần mảng h)
  46.     for (int mask = 0; mask < size; ++mask) {
  47.         unsigned int* fm = f[mask];
  48.         unsigned long long P[24] = {0};
  49.  
  50.         // Tính f * f
  51.         for (int i = 0; i <= n; ++i) {
  52.             unsigned long long fi = fm[i];
  53.             if (!fi) continue;
  54.             for (int j = 0; i + j <= n; ++j) {
  55.                 P[i + j] += fi * fm[j];
  56.             }
  57.             // Mẹo siêu tốc độ: Modulo sau 16 vòng lặp để tránh uint64_t bị tràn
  58.             // Thay vì modulo sau mỗi vòng bên trong, tiết kiệm hàng triệu phép tính
  59.             if (i == 15) {
  60.                 for (int k = 0; k <= n; ++k) P[k] %= MOD;
  61.             }
  62.         }
  63.         for (int k = 0; k <= n; ++k) P[k] %= MOD;
  64.  
  65.         // Tính (f * f) * f
  66.         unsigned long long H[24] = {0};
  67.         for (int i = 0; i <= n; ++i) {
  68.             unsigned long long pi = P[i];
  69.             if (!pi) continue;
  70.             for (int j = 0; i + j <= n; ++j) {
  71.                 H[i + j] += pi * fm[j];
  72.             }
  73.             if (i == 15) {
  74.                 for (int k = 0; k <= n; ++k) H[k] %= MOD;
  75.             }
  76.         }
  77.  
  78.         // Cập nhật lại mảng f (In-place)
  79.         for (int k = 0; k <= n; ++k) fm[k] = H[k] % MOD;
  80.     }
  81.  
  82.     // 3. IFMT / Inverse SOS DP
  83.     for (int len = 1; len < size; len <<= 1) {
  84.         for (int i = 0; i < size; i += 2 * len) {
  85.             for (int j = 0; j < len; ++j) {
  86.                 unsigned int *u = f[i + j];
  87.                 unsigned int *v = f[i + len + j];
  88.                 for (int k = 0; k <= n; ++k) {
  89.                     unsigned int diff = v[k] + MOD - u[k];
  90.                     v[k] = (diff >= MOD) ? diff - MOD : diff;
  91.                 }
  92.             }
  93.         }
  94.     }
  95.  
  96.     // 4. In ra kết quả
  97.     for (int i = 0; i < size; ++i) {
  98.         cout << f[i][__builtin_popcount(i)] << (i == size - 1 ? "" : " ");
  99.     }
  100.     cout << "\n";
  101.  
  102.     return 0;
  103. }
  104.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/37NoQI
language:
C++14 (clang 8.0)
created:
1 day 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!