#97. Binomial Convolution

    ID: 97 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>模板DFT(含 NTT)及FFT数论中国剩余定理

Binomial Convolution

当前没有测试数据。

题目描述

这是一道模板题。

给数列 a0,,an,b0,,bma_0, \dots, a_n, b_0, \dots, b_m 和正整数 MM,求数列 c0,,cn+mc_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 $$

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

输入格式

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

接下来一行输入 n+1n + 1 个整数 a0,,ana_0, \dots, a_n

接下来一行输入 m+1m + 1 个整数 b0,,bmb_0, \dots, b_m

输出格式

输出一行 n+m+1n + m + 1 个数,依次输出 c0,c1,,cn+mc_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][5, 46, 27, 156, 100, 450, 540, 840]

数据范围与提示

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

对于另外 20%20\% 的数据,保证 MM 是质数。

对于另外 20%20\% 的数据,保证 MM22 的幂。

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