Bitwise Convolution 4, 5


Submit solution

Points: 25 (partial)
Time limit: 3.0s
Memory limit: 512M

Author:
Problem type
Bitwise Convolution Exercise 4, 5

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 (4\leq K \leq 5) 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

4 4
1 2 1 2
1 2 3 4

Sample Output 1

5 34 3 18 0 0 0 0

Explanation

We are given that K = 4, N = 4, A = \{1, 2, 1, 2\}, B = \{1, 2, 3, 4\}. Let $ denote the convolution operation.

0$0 = 0, so add a_0\cdot b_0 = 1\cdot 1 to c_0.

0$1 = 1, so add a_0\cdot b_1 + a_1\cdot b_0 = 1\cdot 2 + 2\cdot 1 to c_1.

0$2 = 0, so add a_0\cdot b_2 + a_2\cdot b_0 = 1\cdot 3 + 1\cdot 1 to c_0.

0$3 = 1, so add a_0\cdot b_3 + a_3\cdot b_0 = 1\cdot 4 + 2\cdot 1 to c_1.

\ldots

We already see from above that c_0 = 5


Comments

There are no comments at the moment.