UOJ Logo Zijian Online Judge

ZOJ

#33. 快速沃尔什变换

Statistics

这是一道模板题。

今有两个数列 $A_0, A_1, A_2, \cdots , A_n$ 和 $B_0, B_1, B_2, \cdots , B_m$,定义数列 $C$ 由 $A, B$ 两个数列计算而成:

$$ \forall i \in [0, N), C_i = \sum_{j=0}^n \sum_{k=0}^m { [j \oplus k = i] A_j B_k } \\ N = \min_{t \in \mathbb{Z}^+, 2^t \ge n, 2^t \ge m} 2^t $$

现给出 $\oplus$ 运算和 $n, m, A, B$,请你求出 $C$。

输入格式

第一行一个正整数 $type$;$type=1$ 表示 $\oplus$ 为 $\mathrm{or}$(按位或)运算,$type=2$ 表示 $\oplus$ 为 $\mathrm{and}$(按位与)运算,$type=3$ 表示 $\oplus$ 为 $\mathrm{xor}$(按位异或)运算。

第二行两个正整数 $n, m$。

第三行 $n+1$ 个整数表示 $A_0, A_1, A_2, \cdots , A_n$。

第四行 $m+1$ 个整数表示 $B_0, B_1, B_2, \cdots , B_m$。

输出格式

$N$ 个整数,分别表示 $C_0, C_1, C_2, \cdots , C_{N-1}$ 对 $998244353$ 取模后的结果。

样例一

input

1
2 3
1 2 3
3 4 1 2

output

3 18 13 26

样例二

input

2
2 3
1 2 3
3 4 1 2

output

39 12 9 0

样例三

input

3
2 3
1 2 3
3 4 1 2

output

14 16 14 16

限制与约定

测试点$type$$n, m$
$1, 2$$1$$\le 3000$
$3 \sim 5$$\le 10^5$
$6, 7$$2$$\le 3000$
$8 \sim 10$$\le 10^5$
$10, 11$$3$$\le 3000$
$12 \sim 15$$\le 10^5$

对于 $100\%$ 的数据,保证 $1 \le type \le 3, 1 \le n, m \le 10^5, 0 \le A_i, B_i < 998244353$。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$