Bitwise Convolution 4, 5
Bitwise Convolution Exercise 4, 5
Exercise 1: Bitwise XOR convolution
Exercise 2: Bitwise OR convolution
Exercise 3: Bitwise AND convolution
Exercise 4: An operation that ORs the first bit, ANDs the second bit, and then repeats.
Exercise 5: An operation that ORs the first bit, ANDs the second bit, XORs the third one, and then repeats.
Exercise 6: XOR in base 3 (addition with no carry).
Input and Output Specification
The first line contains the integers (
) and
(
), the exercise number and the length of the vectors
and
. The next line will contain
and the line after will contain
.
You will ouput the vector up until the last non-zero entry, where
is the convolution operation of the respective subtask. Please output these numbers modulo
.
Sample Input 1
4 4
1 2 1 2
1 2 3 4
Sample Output 1
5 34 3 18
Explanation
We are given that . Let
denote the convolution operation.
, so add
to
.
, so add
to
.
, so add
to
.
, so add
to
.
We already see from above that
Sample Input 2
5 2
0 0
0 0
Sample Output 2
Comments