[AdditionalFile174.zip](file://AdditionalFile174.zip?type=additional_file)

#174. 二项卷积

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB 通过: 27 | 提交: 63

题目描述

这是一道模板题。

给数列 $a_0, \dots, a_n, b_0, \dots, b_m$ 和正整数 $M$，求数列 $c_0, \dots, c_{n+m}$，满足：

$$c_k = \sum_{i=\max(k-m,0)}^{\min(k,n)} \binom{k}{i} a_i b_{k-i} \bmod M$$

其中 $\binom{k}{i} = \frac{k!}{i!(k-i)!}$ 是组合数。

输入格式

第一行输入三个正整数 $n, m, M$。

接下来一行输入 $n + 1$ 个整数 $a_0, \dots, a_n$。

接下来一行输入 $m + 1$ 个整数 $b_0, \dots, b_m$。

输出格式

输出一行 $n + m + 1$ 个数，依次输出 $c_0, c_1, \dots, c_{n+m}$。

样例

输入

2 5 114
5 1 4
1 9 1 9 8 10

输出

5 46 27 42 100 108 84 42

取模前的数列是 $[5, 46, 27, 156, 100, 450, 540, 840]$。

数据范围与提示

对于 10% 的数据，保证 $n, m \le 10^3$。

对于另外 20% 的数据，保证 $M$ 是质数。

对于另外 20% 的数据，保证 $M$ 是 2 的幂。

对于 100% 的数据，保证 $0 \le n, m \le 10^5, 2 \le M \le 10^9, 0 \le a_i, b_j < M$。