P9453 [ZSHOI-R1] Effective Strikes.

Tired of fighting the original bosses, FyFive decided to make a Hollow Knight Mod Boss called “Successful Champion”.

Similar to the original Failed Champion, the Successful Champion also has a big armor that cannot be “healed by soul”. However, what makes the Successful Champion harder is that its armor can only be damaged with a specific striking pattern. A strike sequence that can deal damage is called an “effective strike”. As the designer of this Mod Boss, FyFive set a “standard sequence” that can produce effective strikes. To reduce the difficulty of execution, an effective strike can be produced as long as the strike order is “similar” to the standard sequence. Here, “similar” means: for a strike sequence, if you scale the lengths of all consecutive blocks of identical strikes by the same factor, and can obtain another sequence, then the two sequences are said to be “similar”. For example: - ``112244`` and ``111222444`` are similar. - ``111333`` and ``13`` are also similar. - ``226`` and ``226`` are also similar. - ``33889`` and ``33388899`` are not similar. Since the Boss is still in the stage of tuning the standard sequence, FyFive set the Boss’s HP to infinity. But then he cannot compute how many effective strikes his strike sequence produces under the current standard sequence by comparing the initial HP and the final HP. So please help FyFive. **Note**: If it is possible to produce multiple effective strikes at the same time, then multiple effective strikes are indeed produced. For example, when the strike sequence is ``11`` and the standard sequence is ``1``, this strike sequence produces $3$ effective strikes, because the first ``1`` and the second ``1`` are both similar to the standard sequence, and ``11`` is also similar to the standard sequence. If the standard sequence is ``11``, there are also $3$ effective strikes. If the standard sequence is ``12``, then no effective strike is produced. Similarly, when the strike sequence is ``6666`` and the standard sequence is ``66``, then a total of $10$ effective strikes are produced. #### Formally, > Definition: Let sequence $\Alpha$ be > $$\underbrace{AA...A}_{a_1个}\underbrace{BB...B}_{a_2个}\underbrace{CC...C}_{a_3个}...$$ > and sequence $\Beta$ be > $$\underbrace{AA...A}_{b_1个}\underbrace{BB...B}_{b_2个}\underbrace{CC...C}_{b_3个}...$$ > where $A,B,C,a_1,a_2,a_3,...,b_1,b_2,b_3,...\in N_+$。 > > If $\frac{a_1}{b_1}=\frac{a_2}{b_2}=\frac{a_3}{b_3}=...=k\ , k>0$, then $\Alpha$ and $\Beta$ are called similar sequences to each other. > > In particular, a sequence of length $0$ is not similar to any sequence. > > It is not hard to prove that under this definition, similarity between sequences is transitive. Given sequence $A$, compute how many substrings are similar to the given sequence $B$.

The first line contains two integers $n,m$. The second line contains $n$ integers, representing the strike sequence $A$, separated by spaces. The third line contains $m$ integers, representing the standard sequence $B$, separated by spaces.

Output one positive integer in a single line, representing the total number of effective strikes.

Constraints: | Test Point | n | m | Special Property | | :----------: | :----------: | :----------: | :----------: | | 1~2 | $\leq 20000$ | $\leq 20000$ | None | | 3~4 | $\leq 5 \times 10^6$ | $\leq 5 \times 10^6$ | A | | 5~6 | $\leq 5 \times 10^6$ | $\leq 5 \times 10^6$ | B | | 7~10 | $\leq 5 \times 10^6$ | $\leq 5 \times 10^6$ | C | For $100\%$ of the testdata, it is guaranteed that for all $i\in[1,n]$, $1\leq A_i \leq 7$; and for all $i\in[1,m]$, $1\leq B_i\leq 7$. For $100\%$ of the testdata, it is guaranteed that $1\leq n,m\leq 5 \times 10^6$. Special property A: It is guaranteed that $\forall\ i,j\in [1,m]，B_i=B_j$。 Special property B: It is guaranteed that there exists exactly one $k\in[1,m-1]$ such that $\forall \ i,j\in[1,k]$，$B_i=B_j$; and $\forall \ i,j\in[k+1,m]$，$B_i=B_j$。 Special property C: It is guaranteed that in the 10th test point, $n,m \leq 5\times 10^5$, and in the other test points, there are no more than $100$ different lengths of consecutive blocks. Translated by ChatGPT 5