CF1097H Mateusz and an Infinite Sequence

A Thue-Morse-Radecki-Mateusz sequence (Thorse-Radewoosh sequence in short) is an infinite sequence constructed from a finite sequence $ \mathrm{gen} $ of length $ d $ and an integer $ m $ , obtained in the following sequence of steps: - In the beginning, we define the one-element sequence $ M_0=(0) $ . - In the $ k $ -th step, $ k \geq 1 $ , we define the sequence $ M_k $ to be the concatenation of the $ d $ copies of $ M_{k-1} $ . However, each of them is altered slightly — in the $ i $ -th of them ( $ 1 \leq i \leq d $ ), each element $ x $ is changed to $ (x+\mathrm{gen}_i) \pmod{m} $ . For instance, if we pick $ \mathrm{gen} = (0, \color{blue}{1}, \color{green}{2}) $ and $ m = 4 $ : - $ M_0 = (0) $ , - $ M_1 = (0, \color{blue}{1}, \color{green}{2}) $ , - $ M_2 = (0, 1, 2, \color{blue}{1, 2, 3}, \color{green}{2, 3, 0}) $ , - $ M_3 = (0, 1, 2, 1, 2, 3, 2, 3, 0, \color{blue}{1, 2, 3, 2, 3, 0, 3, 0, 1}, \color{green}{2, 3, 0, 3, 0, 1, 0, 1, 2}) $ , and so on. As you can see, as long as the first element of $ \mathrm{gen} $ is $ 0 $ , each consecutive step produces a sequence whose prefix is the sequence generated in the previous step. Therefore, we can define the infinite Thorse-Radewoosh sequence $ M_\infty $ as the sequence obtained by applying the step above indefinitely. For the parameters above, $ M_\infty = (0, 1, 2, 1, 2, 3, 2, 3, 0, 1, 2, 3, 2, 3, 0, 3, 0, 1, \dots) $ . Mateusz picked a sequence $ \mathrm{gen} $ and an integer $ m $ , and used them to obtain a Thorse-Radewoosh sequence $ M_\infty $ . He then picked two integers $ l $ , $ r $ , and wrote down a subsequence of this sequence $ A := ((M_\infty)_l, (M_\infty)_{l+1}, \dots, (M_\infty)_r) $ . Note that we use the $ 1 $ -based indexing both for $ M_\infty $ and $ A $ . Mateusz has his favorite sequence $ B $ with length $ n $ , and would like to see how large it is compared to $ A $ . Let's say that $ B $ majorizes sequence $ X $ of length $ n $ (let's denote it as $ B \geq X $ ) if and only if for all $ i \in \{1, 2, \dots, n\} $ , we have $ B_i \geq X_i $ . He now asks himself how many integers $ x $ in the range $ [1, |A| - n + 1] $ there are such that $ B \geq (A_x, A_{x+1}, A_{x+2}, \dots, A_{x+n-1}) $ . As both sequences were huge, answering the question using only his pen and paper turned out to be too time-consuming. Can you help him automate his research?

N/A

N/A

Thorse-Radewoosh sequence in the first example is the standard Thue-Morse sequence, so the sequence $ A $ is as follows: $ 11010011001011010010 $ . Here are the places where the sequence $ B $ majorizes $ A $ :