結果

問題 No.1901 bitwise xor convolution (characteristic 2)
ユーザー risujiroh
提出日時 2022-04-12 22:54:13
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,615 ms / 4,000 ms
コード長 1,422 bytes
コンパイル時間 11,406 ms
コンパイル使用メモリ 372,084 KB
最終ジャッジ日時 2025-01-28 17:32:56
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC target("pclmul", "sse2", "sse4.1")

#include <bits/stdc++.h>
#include <x86intrin.h>

__int64_t clmul(__int64_t x, __int64_t y) {
  __m128i x_ = _mm_set_epi64x(0, x);
  __m128i y_ = _mm_set_epi64x(0, y);
  __m128i z_ = _mm_clmulepi64_si128(x_, y_, 0);
  return _mm_extract_epi64(z_, 0);
}

int main() {
  using namespace std;
  cin.tie(nullptr)->sync_with_stdio(false);

  int n;
  cin >> n;
  vector<__int64_t> a(1 << n);
  vector<__int64_t> b(1 << n);
  for (__int64_t& e : a) {
    for (int i = 0; i <= 31; ++i) {
      __int64_t x;
      cin >> x;
      e |= x << i;
    }
  }
  for (__int64_t& e : b) {
    for (int i = 0; i <= 31; ++i) {
      __int64_t x;
      cin >> x;
      e |= x << i;
    }
  }

  vector<__int64_t> c(1 << n);

  auto go = [&](auto self, int l, int r) -> void {
    if (l + 1 == r) {
      c[l] = clmul(a[l], b[l]);
      return;
    }

    int m = (l + r) >> 1;

    self(self, l, m);

    self(self, m, r);

    for (int i = l, j = m; j < r; ++i, ++j) { c[i] ^= c[j]; }

    for (int i = l, j = m; j < r; ++i, ++j) {
      a[j] ^= a[i];
      b[j] ^= b[i];
    }

    self(self, m, r);

    for (int i = l, j = m; j < r; ++i, ++j) {
      a[j] ^= a[i];
      b[j] ^= b[i];
    }

    for (int i = l, j = m; j < r; ++i, ++j) { c[j] ^= c[i]; }
  };
  go(go, 0, 1 << n);

  for (__int64_t e : c) {
    for (int i = 0; i <= 62; ++i) { cout << (e >> i & 1) << " \n"[i == 62]; }
  }
}
0