310300: CF1811G1. Vlad and the Nice Paths (easy version)
Description
This is an easy version of the problem, it differs from the hard one only by constraints on $n$ and $k$.
Vlad found a row of $n$ tiles and the integer $k$. The tiles are indexed from left to right and the $i$-th tile has the color $c_i$. After a little thought, he decided what to do with it.
You can start from any tile and jump to any number of tiles right, forming the path $p$. Let's call the path $p$ of length $m$ nice if:
- $p$ can be divided into blocks of length exactly $k$, that is, $m$ is divisible by $k$;
- $c_{p_1} = c_{p_2} = \ldots = c_{p_k}$;
- $c_{p_{k+1}} = c_{p_{k+2}} = \ldots = c_{p_{2k}}$;
- $\ldots$
- $c_{p_{m-k+1}} = c_{p_{m-k+2}} = \ldots = c_{p_{m}}$;
Your task is to find the number of nice paths of maximum length. Since this number may be too large, print it modulo $10^9 + 7$.
InputThe first line of each test contains the integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.
The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 100$) — the number of tiles in a row and the length of the block.
The second line of each test case contains $n$ integers $c_1, c_2, c_3, \dots, c_n$ ($1 \le c_i \le n$) — tile colors.
It is guaranteed that the sum of $n^3$ over all test cases does not exceed $5 \cdot 10^6$.
OutputPrint $t$ numbers, each of which is the answer to the corresponding test case — the number of nice paths of maximum length modulo $10^9 + 7$.
ExampleInput5 5 2 1 2 3 4 5 7 2 1 3 1 3 3 1 3 11 4 1 1 1 1 1 1 1 1 1 1 1 5 2 1 1 2 2 2 5 1 1 2 3 4 5Output
1 4 165 3 1Note
In the first sample, it is impossible to make a nice path with a length greater than $0$.
In the second sample, we are interested in the following paths:
- $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$
- $2 \rightarrow 4 \rightarrow 5 \rightarrow 7$
- $1 \rightarrow 3 \rightarrow 5 \rightarrow 7$
- $1 \rightarrow 3 \rightarrow 4 \rightarrow 7$
In the third example, any path of length $8$ is nice.
Input
题意翻译
这是这道题的简单版本，与困难版本的区别是 $n$ 和 $k$ 的限制。 Ly 有 $n$ 个粉丝，和一个整数 $k$，第 $i$ 个粉丝的颜色是 $c_i$。 Ly 想观看他的粉丝对他的膜拜程度，他会从任意一个粉丝开始，每次向前跳到任意一个粉丝，并且随时可以终止，这样形成了一个路径。 我们定义一个长度为 $m$ 的路径 $p$ 是好的路径，有以下条件： - $m$ 是 $k$ 的倍数。 - $c_{p_1} = c_{p_2} = \cdots = c_{p_k}$。 - $c_{p_{k+1}}=c_{p_{k+2}}=\cdots=c_{p_{2k}}$ - $\cdots$ - $c_{p_{m-k+1}}=c_{p_{m-k+2}}=\cdots=c_{p_m}$ 你的任务是找出最长的好路径的**数量**。答案对 $10^9+7$ 取余。 507348 翻译。Output
这是一个简化版本的问题，与困难版本的区别仅在于对n和k的限制。
Vlad找到了一行n个瓦片和整数k。瓦片从左到右编号，第i个瓦片的颜色为c_i。他决定对其进行操作。
可以从任一瓦片开始，向右跳过任意数量的瓦片，形成路径p。如果满足以下条件，则称长度为m的路径p为“好路径”：
- p可以划分为长度恰好为k的块，即m能被k整除；
- c_{p_1} = c_{p_2} = … = c_{p_k}；
- c_{p_{k+1}} = c_{p_{k+2}} = … = c_{p_{2k}}；
- …
- c_{p_{m-k+1}} = c_{p_{m-k+2}} = … = c_{p_{m}}；
任务是找到最大长度的好路径的数量。由于这个数字可能太大，所以将其模10^9 + 7后输出。
输入数据格式：
每个测试的第一行包含整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例的第一行包含两个整数n和k（1≤k≤n≤100）——瓦片的行数和块长度。
每个测试用例的第二行包含n个整数c_1, c_2, c_3, …, c_n（1≤c_i≤n）——瓦片的颜色。
保证所有测试用例的n^3之和不超过5 * 10^6。
输出数据格式：
输出t个数字，每个数字对应一个测试用例的答案——最大长度的好路径的数量模10^9 + 7。
示例输入输出（提供了一些测试用例的输入输出对，用于理解题意和验证答案）：
输入：
```
5
5 2
1 2 3 4 5
7 2
1 3 1 3 3 1 3
11 4
1 1 1 1 1 1 1 1 1 1 1
5 2
1 1 2 2 2
5 1
1 2 3 4 5
```
输出：
```
1
4
165
3
1
```
注意：
在第一个样本中，无法制作长度大于0的好路径。
在第二个样本中，我们关注以下路径：
- 1 → 3 → 4 → 5
- 2 → 4 → 5 → 7
- 1 → 3 → 5 → 7
- 1 → 3 → 4 → 7
在第三个示例中，任何长度为8的路径都是好路径。题目大意： 这是一个简化版本的问题，与困难版本的区别仅在于对n和k的限制。 Vlad找到了一行n个瓦片和整数k。瓦片从左到右编号，第i个瓦片的颜色为c_i。他决定对其进行操作。 可以从任一瓦片开始，向右跳过任意数量的瓦片，形成路径p。如果满足以下条件，则称长度为m的路径p为“好路径”： - p可以划分为长度恰好为k的块，即m能被k整除； - c_{p_1} = c_{p_2} = … = c_{p_k}； - c_{p_{k+1}} = c_{p_{k+2}} = … = c_{p_{2k}}； - … - c_{p_{m-k+1}} = c_{p_{m-k+2}} = … = c_{p_{m}}； 任务是找到最大长度的好路径的数量。由于这个数字可能太大，所以将其模10^9 + 7后输出。 输入数据格式： 每个测试的第一行包含整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含两个整数n和k（1≤k≤n≤100）——瓦片的行数和块长度。 每个测试用例的第二行包含n个整数c_1, c_2, c_3, …, c_n（1≤c_i≤n）——瓦片的颜色。 保证所有测试用例的n^3之和不超过5 * 10^6。 输出数据格式： 输出t个数字，每个数字对应一个测试用例的答案——最大长度的好路径的数量模10^9 + 7。 示例输入输出（提供了一些测试用例的输入输出对，用于理解题意和验证答案）： 输入： ``` 5 5 2 1 2 3 4 5 7 2 1 3 1 3 3 1 3 11 4 1 1 1 1 1 1 1 1 1 1 1 5 2 1 1 2 2 2 5 1 1 2 3 4 5 ``` 输出： ``` 1 4 165 3 1 ``` 注意： 在第一个样本中，无法制作长度大于0的好路径。 在第二个样本中，我们关注以下路径： - 1 → 3 → 4 → 5 - 2 → 4 → 5 → 7 - 1 → 3 → 5 → 7 - 1 → 3 → 4 → 7 在第三个示例中，任何长度为8的路径都是好路径。