結果

問題 No.1901 bitwise xor convolution (characteristic 2)
ユーザー risujirohrisujiroh
提出日時 2022-04-12 22:54:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,762 ms / 4,000 ms
コード長 1,422 bytes
コンパイル時間 3,792 ms
コンパイル使用メモリ 305,848 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 09:53:29
合計ジャッジ時間 17,339 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2,760 ms
6,944 KB
testcase_08 AC 2,762 ms
6,940 KB
testcase_09 AC 2,739 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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