#P18871. [HONI 2024/2025 #1] Učiteljica
[HONI 2024/2025 #1] Učiteljica
题目描述
给定长度为 的数列。你可以从开头和结尾各删去若干元素,保留一个连续子数组。对于每个 ,保留的子数组中都必须至少有一种数值恰好出现 次。
求满足条件的删除方案数。只要保留的位置集合不同,便视为不同方案。
输入格式
第一行两个整数 ,满足 、。第二行 个整数 ,满足 。
输出格式
输出符合条件的删除方案数。
子任务
| 子任务 | 分值 | 额外限制 |
|---|---|---|
| 1 | 20 | |
| 2 | 15 | 所有 |
| 3 | 35 | |
| 4 | 50 | 无 |
样例
样例 1
输入
3 1
1 2 1
输出
6
样例 2
输入
6 3
6 5 6 4 5 5
输出
1
样例 3
输入
6 2
5 4 5 2 6 5
输出
5