Mừng giao diện mới

Points: 300.00 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Author:

LeKienThanh

Problem type

Allowed languages

C, C++, GAS64, ~~Java~~, Pascal, Perl, PHP, Python, Sed, TCL, Text

Nhân dịp web trường đổi giao diện mới, LeKienThanh đã nghĩ ra một bài toán thú vị sau:
Cho hai số nguyên dương $n$ và $m$ , cùng với hai dãy $A$ và $B$ có độ dài $2^{n}$ và được đánh số từ 0 đến $2^{n} - 1$ . Ta có dãy $C$ cũng có độ dài $2^{n}$ và được đánh số từ $0$ đến $2^{n} - 1$ , được tính toán theo công thức sau:

C [k] = \sum_{i \lor j = k} A [i] * B [j]

Chú thích:

\lor

là phép toán OR.

Đáng tiếc thay, vì LeKienThanh rất gà, chỉ đạt nhì VOI chứ không vào nổi TST, nên anh ấy không biết cách giải bài toán này khi $n$ trở nên quá lớn. Các bạn lập trình viên hãy chứng minh bạn pro hơn LeKienThanh và xứng đáng vào vòng 2 nhé.

Input:

Dòng thứ nhất chứa hai số nguyên dương $n$ và $m$ ( $100 \leq m \leq 999$ )

Dòng thứ hai chứa $2^{n}$ số nguyên trong khoảng $[0, m)$ là các phần tử của dãy $A$ .

Dòng thứ ba chứa $2^{n}$ số nguyên trong khoảng $[0, m)$ là các phần tử của dãy $B$ .

Output:

In ra $2^{n}$ phần tử của dãy $C$ chia dư cho $m$ .

Sample Input:

Copy

2 999
1 2 3 4
5 6 7 8

Sample Output:

Copy

5 28 43 184

Subtask 1: (50% số điểm): $n \leq 10$ .
Subtask 2: (50% số điểm): $n \leq 20$ .

Comments

Please read the guidelines before commenting.

1

UltimateWiener commented 1:47:39 pm, 27/08/2023

easy problem https://codeforces.com/blog/entry/115438