Mateusz and an Infinite Sequence

题意翻译

### 题目描述 给出整数 $m,d$ 和一个序列 $\textrm{gen}$，保证 $\textrm{gen}_1 = 0$。 对两个整数序列 $S$ 和 $T$ 定义 $S+T$ 表示将序列 $T$ 拼接在序列 $S$ 后得到的序列； 对于一个整数序列 $S$ 和一个整数 $x$ 定义 $S+x$ 表示对序列 $S$ 中的所有数 $p$ 进行操作 $p \leftarrow (p+x) \bmod m$ 得到的序列； 定义序列 $M_i$： - 如果 $i=0$，则 $M_i = \{0\}$ - 否则 $M_i = (M_{i-1}+\textrm{gen}_1)+(M_{i-1} + \textrm{gen}_2) + \ldots + (M_{i-1} + \textrm{gen}_d)$。 因为 $\textrm{gen}_1=0$，所以对于 $i>0$，$M_{i-1}$ 是 $M_i$ 的前缀，故 $M_\infty$ 是良定义的。 接下来给出一个长度为 $n$ 的序列 $B$ 和两个整数 $l,r$，定义序列 $A$ 表示 $M_\infty$ 中第 $l$ 到第 $r$ 个元素依次形成的序列，注意序列下标从 $1$ 开始。 定义序列 $P$ 严格大于序列 $Q$ 当且仅当 $|P| = |Q|$ 且 $\forall i \in[1,|Q|],P_i \geq Q_i$。 对于序列 $A$ 的 $|A|-n+1$ 个长度为 $n$ 的连续子串，你需要给出其中 $B$ 严格大于的子串有多少个。 ### 输入格式 第一行两个整数 $d,m(2 \leq d \leq 20,2 \leq m \leq 60)$，第二行 $d$ 个整数描述序列 $\textrm{gen}$，$0 < \textrm{gen}_i \leq 60,\textrm{gen}_1 = 0$。 接下来一行一个整数 $n(1 \leq n \leq 3 \times 10^4)$，接下来 $n$ 个整数描述序列 $B,0 \leq B_i < m$。 最后一行两个整数 $l,r(1 \leq l \leq r \leq 10^{18},r-l+1 \geq n)$ 描述序列 $A$。 ### 输出格式 一行一个整数表示答案。

题目描述

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?

输入输出格式

输入格式

The first line contains two integers $ d $ and $ m $ ( $ 2 \leq d \leq 20 $ , $ 2 \leq m \leq 60 $ ) — the length of the sequence $ \mathrm{gen} $ and an integer used to perform the modular operations. The second line contains $ d $ integers $ \mathrm{gen}_i $ ( $ 0 \leq \mathrm{gen}_i < m $ ). It's guaranteed that the first element of the sequence $ \mathrm{gen} $ is equal to zero. The third line contains one integer $ n $ ( $ 1 \leq n \leq 30000 $ ) — the length of the sequence $ B $ . The fourth line contains $ n $ integers $ B_i $ ( $ 0 \leq B_i < m $ ). The fifth line contains two integers $ l $ and $ r $ ( $ 1 \leq l \leq r \leq 10^{18} $ , $ r-l+1 \geq n $ ).

输出格式

Print a single integer — the answer to the problem.

输入输出样例

输入样例 #1

2 2
0 1
4
0 1 1 0
2 21

输出样例 #1

6

输入样例 #2

3 4
0 1 2
2
0 2
6 11

输出样例 #2

1

说明

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 $ :