No.1901 bitwise xor convolution (characteristic 2)
タグ : / 解いたユーザー数 13
作問者 :
noshi91
/ テスター :
akakimidori
Problem Statement
You are given sequences $(A_0, A_1, \dots, A_{2^n - 1}), (B_0, B_1, \dots, B_{2^n - 1})$ of polynomials with integer coefficients. Compute the sequence $(C_0, C_1, \dots, C_{2^n - 1})$ defined by $$C_k := \left( \sum_{i \oplus j = k} A_i B_j \right) \bmod 2$$ Here, $\oplus$ denotes bitwise xor.
Notes
An instruction that quickly computes the convolution $\bmod 2$ of integers interpreted as sequences of bits is available, at least in C++ (GCC) on yukicoder. Rust also seems to have a similar instruction.
#pragma GCC target("pclmul", "sse2", "sse4.1")
#include <emmintrin.h>
#include <smmintrin.h>
#include <wmmintrin.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);
}
/*
0 <= x, y < 2**32 のとき以下のコードと同じ結果になります。
__int64_t clmul(__int64_t x, __int64_t y) {
__int64_t z = 0;
for (int i = 0; i < 32; i++) {
if (y >> i & 1) {
z ^= x << i;
}
}
return z;
}
*/
Input
$n$
$a_{0, 0}~a_{0, 1}~\dots~a_{0, 31}$
$a_{1, 0}~a_{1, 1}~\dots~a_{1, 31}$
$\vdots$
$a_{2^n-1, 0}~a_{2^n-1, 1}~\dots~a_{2^n-1, 31}$
$b_{0, 0}~b_{0, 1}~\dots~b_{0, 31}$
$b_{1, 0}~b_{1, 1}~\dots~b_{1, 31}$
$\vdots$
$b_{2^n-1, 0}~b_{2^n-1, 1}~\dots~b_{2^n-1, 31}$
This input means that $\displaystyle A_i = \sum_{j=0}^{31}a_{i, j} x^j$. The same applies to $B$.
Input Constraints
- $0 \leq n \leq 17$
- $0 \leq a_{i, j} \lt 2$
- $0 \leq b_{i, j} \lt 2$
Output
$c_{0, 0}~c_{0, 1}~\dots~c_{0, 62}$
$c_{1, 0}~c_{1, 1}~\dots~c_{1, 62}$
$\vdots$
$c_{2^n-1, 0}~c_{2^n-1, 1}~\dots~c_{2^n-1, 62}$
Output $c_{i,j}$ satisfying $\displaystyle C_i = \sum_{j=0}^{62}c_{i,j}x^j$. Print a newline at the end.
Output Constraints
- $0 \leq c_{i, j} \lt 2$
Sample
Sample 1
Input
0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample 2
Input
1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output
1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample 3
Input
3 1 0 1 0 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0
Output
0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 1 0 0 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。