Bitwise Convolution 1, 2, 3


Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type
Bitwise Convolution Exercises 1, 2, 3

This is a practice problem for bitwise convolution using the Fast Walsh–Hadamard transform. Exercises come from here.

  1. Exercise 1: Bitwise XOR convolution

  2. Exercise 2: Bitwise OR convolution

  3. Exercise 3: Bitwise AND convolution

  4. Exercise 4: An operation that ORs the first bit, ANDs the second bit, and then repeats.

  5. Exercise 5: An operation that ORs the first bit, ANDs the second bit, XORs the third one, and then repeats.

  6. Exercise 6: XOR in base 3 (addition with no carry).

Input and Output Specification

The first line contains the integers K (1\leq K \leq 3) and N (N \leq 2\cdot 10^5), the exercise number and the length of the vectors A and B. The next line will contain A and the line after will contain B.

You will ouput a vector of length 2N, the vector C = A$B, where $ is the convolution operation of the respective subtask. Please output these numbers modulo 10^9+9.

Sample Input 1

1 2
1 2
3 4

Sample Output 1

11 10 0 0

Explanation

We are given that K = 1, N = 2, A = \{1, 2\}, B = \{3, 4\}. K = 1, so let \oplus denote the bitwise XOR operation.

C_0 = A_0\oplus B_0 + A_1\oplus B_1 = 1\cdot 3 + 2\cdot 4 = 11

C_1 = A_1\oplus B_0 + A_0\oplus B_1 = 1\cdot 4 + 2\cdot 3 = 10

C_2 = A_2\oplus B_0 + \ldots = 0

Sample Input 2

3 2
1 2
3 4

Sample Output 2

13 8 0 0

Explanation

We are given that K = 3, N = 2, A = \{1, 2\}, B = \{3, 4\}. K = 3, so let \& denote the bitwise AND operation.

C_0 = A_0\& B_0 + A_0\& B_1 + A_1\& B_0 = 1\cdot 3 + 1\cdot 4 + 2\cdot3 = 13

C_1 = A_1\& B_1 = 2\cdot 4 = 8

C_2 = A_2\& B_2 + \ldots = 0


Comments

There are no comments at the moment.