[2015 湖南省队集训] A
题目描述
给定两个非负整数序列 f=(f0,…,fN−1) 和 c=(c0,…,cM−1),下标从 0 开始。对 f 执行一次操作时,产生长为 N 的新序列 f′,其中
fi′=j=0∑M−1fi−cj(0≤i<N),
并规定当 i−cj<0 时该项为 0。本次操作的右侧全部取自操作前的序列。操作完成后,用 f′ 替换 f。
c 中可以有重复值,每次出现都单独计入;且至少有一个 cj=0。
求执行 K 次操作后的序列,各项对 950009857 取模。
输入格式
第一行三个整数 N,M,K。第二行 N 个非负整数,给出初始序列 f。第三行 M 个非负整数,给出序列 c。
输出格式
输出一行 N 个整数,依次表示最终序列各项对 950009857 的非负余数。
样例 #1
样例输入 #1
3 2 2
1 2 3
0 1
样例输出 #1
1 4 8
数据规模与约定
| 数据点 |
N 的上界 |
M 的上界 |
K 的上界 |
备注 |
| 1–3 |
100 |
100 |
|
| 4–5 |
10000 |
100000 |
0≤cj≤3 |
| 6–7 |
|
| 8–10 |
109 |
没有额外限制的数据点满足 0≤cj<N。