126 . 騷擾選手的卷積

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

ioicamp ioicamp-2023

Description

「邊上有一些小 node 但那是來騷擾你們的」——蔡孟宗教授

有些出題者總是喜歡沒事騷擾一下選手（當然，不保證不包含物理上的）。沒錯，這題也是要來騷擾參賽者的。還記得早上講的位元卷積嗎？你說怎麼沒講其他位元運算要怎麼做？喔，那個是你現在應該思考的事。

給定兩個長度為 $N = 2^ K$ 的非負整數序列 $A, B$ ，以及一個長度為 $K$ 、由 $0 \sim 5$ 的整數構成的序列 $X$，請輸出一個長度為 $N$ 的非負整數序列 $C$ ，使得 $C_i = \sum \limits _ {j \oplus k = i} A_j B_k \pmod{998244353}$ 。其中，$\oplus$ 被稱作「騷擾運算子」， $j \oplus k$ 代表以二進位表示 $j$ 和 $k$ 時，第 $d$ 位（由低向高從 0 開始數）要做第 $X_d$ 種位元運算。位元運算的編號如下：

  1. AND
  2. OR
  3. XOR
  4. NAND
  5. NOR
  6. NXOR

Input Format

第一行輸入兩個正整數 $N, K$ 。

接下來兩行分別輸入兩個長度為 $N$ 的非負整數序列 $A, B$ 。

最後輸入一個長度為 $K$ 的非負整數序列 $X$ 。

對於所有測試資料，保證：

  • 所有輸入都是非負整數
  • $K \le 20, N = 2^ K$
  • $0 \le A_i, B_i < 998244353 :\forall i \in [0, N)$
  • $0 \le X_i \le 5 :\forall i \in [0, K)$

Output Format

請輸出一行包含 $N$ 個在 $[0, 998244353)$ 的非負整數，代表 $C$ 。

Sample Input 1

4 2
1 2 3 4
5 6 7 8
0 0

Sample Output 1

103 52 73 32

Sample Input 2

4 2
1 2 3 4
5 6 7 8
1 1

Sample Output 2

5 28 43 184

Sample Input 3

4 2
1 2 3 4
5 6 7 8
2 2

Sample Output 3

70 68 62 60

Sample Input 4

4 2
1 2 3 4
5 6 7 8
3 3

Sample Output 4

32 73 52 103

Sample Input 5

4 2
1 2 3 4
5 6 7 8
4 4

Sample Output 5

184 43 28 5

Sample Input 6

4 2
1 2 3 4
5 6 7 8
5 5

Sample Output 6

60 62 68 70

Sample Input 7

8 3
1 2 3 4 5 6 7 8
7 1 2 2 3 3 4 5
2 0 1

Sample Output 7

40 52 14 14 292 302 130 128

Sample Input 8

8 3
1 2 3 4 5 6 7 8
7 1 2 2 3 3 4 5
3 4 5

Sample Output 8

78 278 12 94 110 310 20 70

Hints

Problem Source

IOICamp 2023 Day5 pA

Subtasks

No. Testdata Range Constraints Score
1 0~7 範例測資 0
2 0, 8~12 $X_i = 0$ 0
3 1, 13~17 $X_i = 1$ 0
4 2, 18~22 $X_i = 2$ 1
5 3, 23~27 $X_i = 3$ 2
6 4, 28~32 $X_i = 4$ 2
7 5, 33~37 $X_i = 5$ 2
8 0~2, 6, 8~22, 38~42 $X_i \in \lbrace 0, 1, 2\rbrace$ 30
9 0~52 無其他限制 63

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2 8 9
1 2000 524288 65536 1 3 8 9
2 2000 524288 65536 1 4 8 9
3 2000 524288 65536 1 5 9
4 2000 524288 65536 1 6 9
5 2000 524288 65536 1 7 9
6 2000 524288 65536 1 8 9
7 2000 524288 65536 1 9
8 2000 524288 65536 2 8 9
9 2000 524288 65536 2 8 9
10 2000 524288 65536 2 8 9
11 2000 524288 65536 2 8 9
12 2000 524288 65536 2 8 9
13 2000 524288 65536 3 8 9
14 2000 524288 65536 3 8 9
15 2000 524288 65536 3 8 9
16 2000 524288 65536 3 8 9
17 2000 524288 65536 3 8 9
18 2000 524288 65536 4 8 9
19 2000 524288 65536 4 8 9
20 2000 524288 65536 4 8 9
21 2000 524288 65536 4 8 9
22 2000 524288 65536 4 8 9
23 2000 524288 65536 5 9
24 2000 524288 65536 5 9
25 2000 524288 65536 5 9
26 2000 524288 65536 5 9
27 2000 524288 65536 5 9
28 2000 524288 65536 6 9
29 2000 524288 65536 6 9
30 2000 524288 65536 6 9
31 2000 524288 65536 6 9
32 2000 524288 65536 6 9
33 2000 524288 65536 7 9
34 2000 524288 65536 7 9
35 2000 524288 65536 7 9
36 2000 524288 65536 7 9
37 2000 524288 65536 7 9
38 2000 524288 65536 8 9
39 2000 524288 65536 8 9
40 2000 524288 65536 8 9
41 2000 524288 65536 8 9
42 2000 524288 65536 8 9
43 2000 524288 65536 9
44 2000 524288 65536 9
45 2000 524288 65536 9
46 2000 524288 65536 9
47 2000 524288 65536 9
48 2000 524288 65536 9
49 2000 524288 65536 9
50 2000 524288 65536 9
51 2000 524288 65536 9
52 2000 524288 65536 9
Submit
Back to Top