【题目描述】
给定 F264 中的元素构成的序列 a0,a1,...,aN−1 和 b0,b1,...,bM−1,按如下方式计算 F264 中的元素构成的序列 c0,c1,...,c(N−1)+(M−1):
ck=i+j=k∑aibj设 P(x)=x64+x4+x3+x+1∈F2[x] 为 F2 上的 64 次不可约多项式。
F264 构造为商环 F2[x]/(P(x))。
F264 中的元素可由其模 P(x) 的余式唯一表示。
F2[x] 中次数小于 64 的多项式可以自然地与无符号 64 位整数等同:对应数字中的第 i 位被置为 1,当且仅当多项式中含单项式 xi。
本题的输入与输出均使用这种整数表示。
提示:_mm_clmulepi64_si128 intrinsic 可能会有帮助。
【输入】
文本
$N$ $M$
$a_0$ $a_1$ ... $a_{N-1}$
$b_0$ $b_1$ ... $b_{M-1}$
【输出】
文本
$c_0$ $c_1$ ... $c_{(N - 1) + (M - 1)}$
【输入样例】
文本
5 7
1 2 3 4 5
6 7 8 9 10 11 12
【输出样例】
文本
6 11 12 8 2 63 8 0 26 23 60
【输入样例2】
文本
1 1
10000000000000000000
10000000000000000000
【输出样例2】
【数据范围】
- 1≤N,M≤524288
- 0≤ai,bi<264
【来源】
Library Checker(yosupo06) convolution_F_2_64