AT1202Contest_h Incomplete Notes

给定两个长度分别为 $ N $ 和 $ M $ 的非负整数序列 $ A\ =\ (A_1,\ \dots,\ A_N) $ 和 $ B\ =\ (B_1,\ \dots,\ B_M) $。 求满足以下条件的整数 $ i $ 的个数，其中 $ 1\ \le\ i\ \le\ N\ -\ M\ +\ 1 $。 **条件** > 定义序列 $ C $ 为由 $ A $ 的长度为 $ M $ 的连续子序列，$ C\ =\ (A_i,\ \dots,\ A_{i\ +\ M\ -\ 1}) $。接下来，将序列 $ B $ 和 $ C $ 中所有值为 $ 0 $ 的元素用任意 正实数 替换（替换后的值可以相同）。然后，对于任意 正实数 $ t $，将序列 $ C $ 的所有元素乘以 $ t $。通过这样的操作，可以使得序列 $ B $ 和 $ C $ 相等。

无

无

### ストーリー あなたは $ N $ 個の音からなる歌が途切れ途切れ聞こえた．この歌に， $ M $ 個の音からなるフレーズが含まれていたかどうかを推測したい．ただし，フレーズが本来と異なる [調](https://ja.wikipedia.org/wiki/%E8%AA%BF) で含まれている場合も考慮したい． ### 制約 - $ 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) $ ### Sample Explanation 1 $ 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 $ を出力します．