結果
問題 |
No.1901 bitwise xor convolution (characteristic 2)
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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]; } } }