1009. 数组

题目描述

给定长为 n 的序列 A = (a1, a2, …, an ) 和长为 2w 的数组

H [0 .. 2w − 1]。对于 1 ≤ i ≤ n，定义∑

Ci =

m

1≤b1,b2,…,bm ≤n

k

H [(∑ abj ) mod 2w ] ⋅ (∑[bj = i]) .m

j=1

j=1

其中，外层求和遍历所有 B = (b1, b2, …, bm ) (1 ≤ bj ≤ n)，[⋅] 为艾

弗森括号。求 C1, C2, …, Cn 对 998 244 353 取模的结果。

输入格式

第一行输入一个正整数 T (1 ≤ T ≤ 35)，表示数据组数。接下来按如下格式输入 T 组数据：第一行输入四个整数 n, w, m, k (1 ≤ n ≤ 5 × 105, 0 ≤ w ≤ 19, 1 ≤

m ≤ 109, 1 ≤ k ≤ 20)。第二行输入 n 个整数表示 A = (a1, a2, ⋯, an ) (0 ≤ ai < 2w )。

第三行输入 2w 个整数表示 H [0 .. 2w − 1] (0 ≤ hi < 2w )。

保证输入数据中 ∑ n, ∑ 2w 均不超过 106。

输出格式

共 T 行，对于每组数据，输出 n 个整数，表示每个数得到的贡献。

样例输入

2
2 2 2 1
0 1
1 1 2 2
4 2 1 1
0 1 2 3
3 3 2 0

样例输出

4 6
3 3 2 0

提示

本题输入输出量较大，建议使用较快速的输入输出方式（如关闭流同步的 cin / cout）。请注意常数因子对程序效率的影响。

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第1场）