← 返回题目列表

Codeforces · 2242/C

C. 不稳定元素

中文机器翻译题面 查看原题

您将获得 已排序 整数数组 $$$[a_1, a_2, \dots, a_n]$$$。我们可以对此数组执行任意数量的以下类型的操作:

  • 标记数组的第一个元素,以及不等于其左邻居的所有元素(即,满足 $$$a_i \ne a_{i-1}$$$ 的所有元素 $$$i$$$)。
  • 然后删除所有标记的元素或复制它们(即,用两个相同的元素替换每个标记的元素)。

例如,考虑数组 $$$[\mathbf{1}, 1, 1, \mathbf{2}, \mathbf{4}, 4, \mathbf{5}]$$$ (标记的元素以粗体显示)。如果我们删除所有标记的元素,我们会得到 $$$[1, 1, 4]$$$,如果我们复制它们,我们会得到 $$$[1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5]$$$。

如果数组变空,则无法执行操作。每次操作后,每个元素都会被取消标记。

如果一个整数数组 $$$b$$$ 可以通过一定数量的所描述的操作从数组 $$$a$$$ 中获得,那么我们称该数组 $$$b$$$ 是可达的。您的任务是计算长度为 $$$k$$$ 的可达数组的数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成:

  • 第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 3 \cdot 10^5$$$);
  • 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le n$$$)。 请注意,数组已排序。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 — 长度为 $$$k$$$ 的可达数组 $$$b$$$ 的数量。可以证明,在问题的约束下,答案符合标准的 $$$32$$$ 位整数类型。

示例

输入
复制

10
1 5
1
4 5
1 1 2 2
3 1
1 1 1
4 8
1 2 3 4
8 6
1 1 1 2 2 2 2 2
6 3
1 1 2 2 3 3
10 7
1 1 1 2 2 3 3 3 3 4
12 5
1 1 1 1 2 2 2 3 3 4 4 4
6 5
1 1 2 2 3 3
3 1
1 2 2

输出
复制

1
0
1
1
2
1
2
1
0
1

注意

在第一个示例中,可以执行以下操作序列:

  • $$$[\mathbf{1}] \rightarrow [\mathbf{1}, 1] \rightarrow [\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1, 1, 1] \rightarrow [1, 1, 1, 1, 1]$$$。

在第二个示例中,不可能获得长度为 $$$5$$$ 的数组。

在第三个示例中,可以执行以下操作序列:

  • $$$[\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1] \rightarrow [1]$$$。

在第五个例子中,可以得到数组$$$[1, 1, 2, 2, 2, 2]$$$和$$$[2, 2, 2, 2, 2, 2]$$$:

  • $$$[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [1, 1, 2, 2, 2, 2]$$$;
  • $$$[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [\mathbf{1}, 1, \mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{1}, \mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2] \rightarrow [\mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2, 2] \rightarrow [2, 2, 2, 2, 2, 2]$$$。

在第七个例子中,可以获得数组$$$[1, 1, 1, 3, 3, 3, 3]$$$和$$$[3, 3, 3, 3, 3, 3, 3]$$$。