#CW11. 数组操作(array)

数组操作(array)

题目描述

现有一个已排序的整数数组 aia_i。可以对该数组进行任意次以下操作:

  • 将所有不等于其左侧相邻元素的元素(即 ai≠ai−1a_i \ne a_{i-1} 的 ii),以及第一个元素(即 i=1i=1),设定为已标记。
  • 删除所有已标记的元素,或在原位置复制一遍它们。

例如,对于数组 [1,1,1,2,4,4,5][1,1,1,2,4,4,5],其第 1,4,5,71,4,5,7 个元素是已标记的。

  • 若删除所有标记元素,则得到 [1,1,4][1,1,4]。
  • 若复制这些标记元素,则得到 [1,1,1,1,2,2,4,4,4,5,5][1,1,1,1,2,2,4,4,4,5,5]。

若数组为空,则无法执行操作。每次操作后,所有元素均会被取消标记。

我们称一个整数数组 bb 为可达的,当且仅当可以通过若干次所述操作,从数组 aa 获得。

请统计长度为 kk 的可达数组的数量。

输入格式

第一行包含两个整数 nn 和 kk。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n。保证该数组已排序。

输出格式

输出一个整数,表示长度为 kk 的可达数组的数量。

样例 1 输入

3 3
2 2 3

样例 1 输出

2

样例 2 输入

10 7
1 1 1 2 2 3 3 3 3 4

样例 2 输出

2

数据范围

对于所有测试数据,保证:1≤n,k≤3×1051 \le n, k \le 3 \times 10^5,1≤a1≤a2≤⋯≤an≤n1 \le a_1 \le a_2 \le \cdots \le a_n \le n。

测试点 n≤n \le 特殊性质
1∼41 \sim 4 55 无
5∼65 \sim 6 100100
7∼107 \sim 10 10001000
11∼1211 \sim 12 3×1053 \times 10^5 k≤10k \le 10
13∼1413 \sim 14 an≤100a_n \le 100
15∼2015 \sim 20 无