题目 30013

卷积(F2^64 域)

查看题解 ↗GitHub ↗如何评测
题号
30013
时间限制
10000 ms
内存限制
1024 MB
标签
数学
来源
Library Checker (yosupo06) - convolution_F_2_64

【题目描述】

给定 F264\mathbb{F} _ {2^{64}} 中的元素构成的序列 a0,a1,...,aN−1a_0, a_1, ..., a_{N - 1} 和 b0,b1,...,bM−1b_0, b_1, ..., b_{M - 1},按如下方式计算 F264\mathbb{F} _ {2^{64}} 中的元素构成的序列 c0,c1,...,c(N−1)+(M−1)c_0, c_1, ..., c_{(N - 1) + (M - 1)}:

ck=∑i+j=kaibjc_k = \sum_{i+j=k} a_ib_j

设 P(x)=x64+x4+x3+x+1∈F2[x]P(x) = x^{64} + x^4 + x^3 + x + 1 \in \mathbb{F}_2[x] 为 F2\mathbb{F}_2 上的 6464 次不可约多项式。 F264\mathbb{F} _ {2^{64}} 构造为商环 F2[x]/(P(x))\mathbb{F}_2[x] / (P(x))。 F264\mathbb{F} _ {2^{64}} 中的元素可由其模 P(x)P(x) 的余式唯一表示。

F2[x]\mathbb{F}_2[x] 中次数小于 6464 的多项式可以自然地与无符号 6464 位整数等同:对应数字中的第 ii 位被置为 11,当且仅当多项式中含单项式 xix^i。 本题的输入与输出均使用这种整数表示。

提示:_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】

文本
9721624009203188202

【数据范围】

  • 1≤N,M≤5242881 \leq N, M \leq 524288
  • 0≤ai,bi<2640 \leq a_i, b_i < 2^{64}

【来源】

Library Checker(yosupo06) convolution_F_2_64

数据下载

题目 30013 的公开数据

正在读取文件列表…

常用命令

题目 30013 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。