题目 30024

乘法幺半群卷积(Z/P Z)

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

【题目描述】

给定素数 PP 以及整数序列 a0,a1,...,aP−1a_0, a_1, ..., a_{P - 1} 和 b0,b1,...,bP−1b_0, b_1, ..., b_{P - 1}。按如下方式计算整数序列 c0,c1,...,cP−1c_0, c_1, ..., c_{P - 1}:

ck=∑i×j≡k(modP)aibj mod 998244353c_k = \sum_{i \times j \equiv k \pmod{P}} a_i b_j \bmod 998244353

【输入】

文本
$P$
$a_0$ $a_1$ ... $a_{P - 1}$
$b_0$ $b_1$ ... $b_{P - 1}$

【输出】

文本
$c_0$ $c_1$ ... $c_{P - 1}$

【输入样例】

文本
5
9 7 5 3 1
8 6 4 2 0

【输出样例】

文本
308 64 60 36 32

【输入样例2】

文本
2
0 998244352
0 998244352

【输出样例2】

文本
0 1

【数据范围】

  • 2≤P≤5242882 \leq P \leq 524288
  • PP 是素数
  • 0≤ai,bi<9982443530 \leq a_i, b_i < 998244353

【来源】

Library Checker(yosupo06) mul_modp_convolution

数据下载

题目 30024 的公开数据

正在读取文件列表…

常用命令

题目 30024 的 ROJ 命令

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