U509539 [COCI2024/2025 #1] Učiteljica

在 Varaždin 最好的学校里，有一位优秀的计算机科学老师，她以其有趣和不寻常的想法而闻名。她的名字叫拉娜，她经常给学生出一些不可能或无法解决的问题。每个学生在学年期间只需要解决一个问题，就可以以优异的成绩通过这门课。那些在学年末没有解决任何任务的学生将不得不重读这个年级。在学年的最后一天，她在黑板上写了一个极其困难的问题，如下所示: 假设您有一个长度为 $N$ 的数列，您可以从开始或结束删除某些元素。您可以通过多少种方式执行这样的删除，以便在删除后，至少有 $1$ 个数字出现一次，至少有 $2$ 个数字出现两次，……，以及至少有 $1$ 个人数字出现 $K$ 次。 一个名叫弗兰的学生，到目前为止还没有解决任何问题。 他说：“我知道如何解决这个问题。” 拉娜老师不相信弗兰，告诉他：“在接下来的 $30$ 分钟内写出代码，然后我相信你。如果你做不到，你就得重修。” 弗兰不知道如何编码，所以他急切地请求你的帮助，编写代码来解决这个任务。在他匆忙中，他忘记解释了解决这个任务的想法。编写一个代码，输入数字 $N$ 和 $K$，$N$ 个元素的序列，解决拉娜的问题，以帮助弗兰。

在第一行，有2个正整数 $N$ 和 $K$，来自任务说明。 在第二行中，有 $N$ 个正整数 $a_i$，这些数字来自任务描述。

仅一行，输出一个整数，即满足任务条件的不同删除次数。如果有一个索引在其中一个中未删除，但在另一个中删除，则两个删除是不同的。

【样例解释 #1】 删除后可能出现的序列为: $\{[1],[2],[1],[1,2],[2,1],[1,2,1]\}$ 并且在 $6$ 个序列中，每个序列中都有一个数字刚好出现一次。 【样例解释 #2】 在删除后的唯一序列中，至少有一个数字恰好出现一次，至少有一个数字恰好出现两次，至少有一个数字恰好出现三次，这个序列就是给定的 $N$ 个数字序列。 【数据范围】 对于 $100\%$ 的数据，保证 $1\le a_i\le N\le 10^5$，$1\le K\le 4$。 | Substask | 分数 | 约束条件 | | :----------: | :----------: | :----------: | | $0$ | $0$ | 样例 | | $1$ | $20$ | $N\le1000$ | | $2$ | $15$ | $1\le a_i\le k$ | | $3$ | $35$ | $k=1$ | | $4$ | $50$ | 无 |