题目 30014

卷积

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

【题目描述】

给定整数序列 a0,a1,...,aN−1a_0, a_1, ..., a_{N - 1} 和 b0,b1,...,bM−1b_0, b_1, ..., b_{M - 1}。按如下方式计算整数序列 c0,c1,...,c(N−1)+(M−1)c_0, c_1, ..., c_{(N - 1) + (M - 1)}:

ck=∑i+j=kaibj mod 998244353c_k = \sum_{i+j=k} a_i b_j \bmod 998244353

【输入】

文本
$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)}$

【输入样例】

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

【输出样例】

文本
5 16 34 60 70 70 59 36

【输入样例2】

文本
1 1
10000000
10000000

【输出样例2】

文本
871938225

【数据范围】

  • 1≤N,M≤5242881 \leq N, M \leq 524288
  • 0≤ai,bi<9982443530 \leq a_i, b_i < 998244353

【来源】

Library Checker(yosupo06) convolution_mod

数据下载

题目 30014 的公开数据

正在读取文件列表…

常用命令

题目 30014 的 ROJ 命令

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