#174. 二项卷积

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

这是一道模板题。

给数列 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