126 . 騷擾選手的卷積

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

85.0% (17/20)

Tags

ioicamp ioicamp-2023

Description

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

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

給定兩個長度為 N=2K 的非負整數序列 A,B ，以及一個長度為 K 、由 0∼5 的整數構成的序列 X，請輸出一個長度為 N 的非負整數序列 C ，使得 Ci=∑j⊕k=iAjBk(mod998244353) 。其中，⊕ 被稱作「騷擾運算子」， j⊕k 代表以二進位表示 j 和 k 時，第 d 位（由低向高從 0 開始數）要做第 Xd 種位元運算。位元運算的編號如下：

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

Input Format

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

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

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

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

  • 所有輸入都是非負整數
  • K≤20,N=2K
  • 0≤Ai,Bi<998244353:∀i∈[0,N)
  • 0≤Xi≤5:∀i∈[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 Xi=0 0
3 1, 13~17 Xi=1 0
4 2, 18~22 Xi=2 1
5 3, 23~27 Xi=3 2
6 4, 28~32 Xi=4 2
7 5, 33~37 Xi=5 2
8 0~2, 6, 8~22, 38~42 Xi∈{0,1,2} 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