#CS2113. 信号与掩码

信号与掩码

题目背景

翻译自 CSES-2113 题。

题目描述

给定两个整数序列：一个信号序列和一个掩码序列。你的任务是通过将掩码从左到右滑动在信号上处理信号。在每个掩码位置，计算信号与掩码重叠部分的对齐信号值和掩码值的乘积和。

输入格式

第一行包含两个整数 n 和 m，分别表示信号的长度和掩码的长度。

第二行包含 n 个整数 a1,a2,...,ana_1, a_2, ..., a_na1​,a2​,...,an​，定义了信号序列。

第三行包含 m 个整数 b1,b2,...,bmb_1, b_2, ..., b_mb1​,b2​,...,bm​，定义了掩码序列。

输出格式

输出 n+m−1n + m - 1n+m−1 个整数，表示每个掩码位置的对齐乘积和，从左到右依次输出。

样例

5 3
1 3 2 1 4
1 2 3

3 11 13 10 16 9 4

样例1解释 例如，在第二个掩码位置，信号和掩码的对齐乘积和是 2×1+3×3=112 \times 1 + 3 \times 3 = 112×1+3×3=11。

说明/提示

$1 \leq n, m \leq 2 \times 10^5$

1≤ai,bi≤1001 \leq a_i, b_i \leq 1001≤ai​,bi​≤100。