← 返回题目列表

AtCoder · 1202Contest_h

H. 注释不完整

中文机器翻译题面 查看原题

分数: 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