Bitwise Convolution 6


Submit solution

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

Authors:
Problem type
Bitwise Convolution Exercise 6

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 (K = 6) 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 3N (not 2N) , the vector C = A$B, where $ is the convolution operation of the respective subtask. Please output these numbers modulo 10^9+9 (not 10^9+7).

Sample Input 1

6 3
1 2 3
1 1 2

Sample Output 1

8 9 7 0 0 0 0 0 0

Explanation

We are given that K = 6, N = 3, A = \{1, 2, 3\}, B = \{1, 1, 2\}. Let \oplus denote the base-3 XOR (sum of digits in base 3 without carrying) operation.

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

0 \oplus 1 = 1, so we add a_0\cdot b_1 = 1\cdot 1 to c_1.

\ldots

1 \oplus 2 = 3 \equiv 0 \pmod 3, so we add a_1\cdot b_2 = 2\cdot 2 to c_0.

\ldots

Sample Input 2

6 4
1 2 2 2
1 1 2 3

Sample Output 2

7 7 6 5 8 10 6 0 0 0 0 0

Comments

There are no comments at the moment.