#P4178. [2015年湖南省队省队集训]A

    ID: 3390 传统题 3000ms 128MiB 尝试: 87 已通过: 39 难度: 7 上传者: 标签>难度分类提高+/省选-多项式与生成函数卷积转化数论快速幂截断幂级数NTTCF2200

[2015年湖南省队省队集训]A

[2015 湖南省队集训] A

题目描述

给定两个非负整数序列 f=(f0,…,fN−1)f=(f_0,\ldots,f_{N-1}) 和 c=(c0,…,cM−1)c=(c_0,\ldots,c_{M-1}),下标从 00 开始。对 ff 执行一次操作时,产生长为 NN 的新序列 f′f',其中

fi′=∑j=0M−1fi−cj(0≤i<N),f'_i=\sum_{j=0}^{M-1} f_{i-c_j} \qquad(0\le i<N),

并规定当 i−cj<0i-c_j<0 时该项为 00。本次操作的右侧全部取自操作前的序列。操作完成后,用 f′f' 替换 ff。

cc 中可以有重复值,每次出现都单独计入;且至少有一个 cj=0c_j=0。

求执行 KK 次操作后的序列,各项对 950009857950009857 取模。

输入格式

第一行三个整数 N,M,KN,M,K。第二行 NN 个非负整数,给出初始序列 ff。第三行 MM 个非负整数,给出序列 cc。

输出格式

输出一行 NN 个整数,依次表示最终序列各项对 950009857950009857 的非负余数。

样例 #1

样例输入 #1

3 2 2
1 2 3
0 1

样例输出 #1

1 4 8

数据规模与约定

数据点 NN 的上界 MM 的上界 KK 的上界 备注
11–33 100100 100100
44–55 10 00010\,000 100 000100\,000 0≤cj≤30\le c_j\le3
66–77
88–1010 10910^9

没有额外限制的数据点满足 0≤cj<N0\le c_j<N。