分数: 100 点
故事
您听到的歌曲包括 N 断断续续地记笔记。您想猜测一个短语是否包含 M 声音包含在这首歌中。您还需要考虑该短语包含在不同的情况中 键 比原来的。
问题陈述
给定两个非负整数序列, A = (A_1, \dots, A_N) 和 B = (B_1, \dots, B_M),每个长度 N 和 M。
查找整数的个数 i 满足 1 \le i \le N - M + 1 并满足以下条件:
状况
定义连续子序列 C 长度 M of A as C = (A_i, \dots, A_{i + M - 1})。接下来,更新序列的所有元素 B 和 C 是 0 与任何 正实数 (每个元素的更新值可能不同)。然后,确定任意一个 正实数 t,并将序列的所有元素相乘 C by t。通过这样做,序列 B 和 C 可以变得相同。
约束
- 1 \leq M \leq N \leq 5 \times 10^5
- 0 \leq A_i \leq 5 \times 10^5 (i = 1, \ldots, N)
- 0 \leq B_i \leq 5 \times 10^5 (i = 1, \ldots, M)
输入
输入由标准输入按以下格式给出:
N \ M A_1 \ A_2 \ \dots \ A_N B_1 \ B_2 \ \dots \ B_M
输出
打印一个整数作为答案。
示例输入 1
9 4 9 3 0 0 2 99 4 0 0 6 2 0 4
示例输出 1
4
对于 i = 1,更新 B to (6, 2, 5, 4) 和 C = (9, 3, 0, 0) to (9, 3, 7.5, 6),并取 t = 2/3。最后, B 和 C 将匹配。
对于 i = 2, 3, 4,可以使 B 和 C 通过执行适当的操作来匹配,但是对于 i = 5, 6,这是不可能的。
因此,自从 i = 1, 2, 3, 4 满足条件,输出 4 作为答案。
示例输入 2
8 2 0 0 0 0 0 0 0 0 0 0
示例输出 2
7