/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 100 点
ストーリー
あなたは N 個の音からなる歌が途切れ途切れ聞こえた．この歌に， M 個の音からなるフレーズが含まれていたかどうかを推測したい．ただし，フレーズが本来と異なる 調 で含まれている場合も考慮したい．
問題文
それぞれ長さが N, M の 2 つの非負整数列 A = (A_1, \dots, A_N), B = (B_1, \dots, B_M) が与えられます．
1 \le i \le N - M + 1 を満たす整数 i のうち，以下の条件を満たすものの個数を求めてください．
条件
A の長さ M の連続部分列 C を C = (A_i, \dots, A_{i + M - 1}) で定める．次に，数列 B, C の各要素のうち値が 0 であるもの全てを任意の 正の実数 で更新する（更新後の値は各要素で異なっていてよい）．その後， 正の実数 t を任意に定め，数列 C の全ての要素に 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 を (6, 2, 5, 4) に，また C = (9, 3, 0, 0) を (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 個が条件を満たすので答えとして 4 を出力します．
入力例 2
8 2 0 0 0 0 0 0 0 0 0 0
出力例 2
7
Score : 100 points
Story
You heard a song consisting of N notes in fits and starts. You want to guess whether a phrase consisting of M sounds was included in this song. You also want to consider cases where the phrase is included in a different key than the original.
Problem Statement
You are given two sequences of non-negative integers, A = (A_1, \dots, A_N) and B = (B_1, \dots, B_M), each of length N and M, respectively.
Find the number of integers i that satisfy 1 \le i \le N - M + 1 and meet the following condition:
Condition
Define a contiguous subsequence C of length M of A as C = (A_i, \dots, A_{i + M - 1}). Next, update all elements of the sequences B and C that are 0 with any positive real number (the updated values may be different for each element). Then, determine an arbitrary positive real number t, and multiply all elements of sequence C by t. By doing so, the sequences B and C can be made identical.
Constraints
- 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)
Input
The input is given from Standard Input in the following format:
N \ M A_1 \ A_2 \ \dots \ A_N B_1 \ B_2 \ \dots \ B_M
Output
Print an integer as the answer.
Sample Input 1
9 4 9 3 0 0 2 99 4 0 0 6 2 0 4
Sample Output 1
4
For i = 1, update B to (6, 2, 5, 4) and C = (9, 3, 0, 0) to (9, 3, 7.5, 6), and take t = 2/3. Finally, B and C will match.
For i = 2, 3, 4, it is possible to make B and C match by performing appropriate operations, but for i = 5, 6, it is impossible.
Therefore, since i = 1, 2, 3, 4 meet the condition, output 4 as the answer.
Sample Input 2
8 2 0 0 0 0 0 0 0 0 0 0
Sample Output 2
7