货物 - 代码源竞赛平台

题目描述

有 $n$ 件货物排成一排，从左到右依次编号为 $1,2,\ldots,n$。第 $i$ 件货物的颜色为 $c_i$，所有颜色用 $1,2,\ldots,m$ 表示。

每次操作，你可以取走当前最左端或最右端的一件货物。你需要恰好进行 $m$ 次操作，使取走的货物中，每种颜色都恰好出现一次。

请求出满足要求的不同取法数量。两种取法不同，当且仅当最终取走的货物编号集合不同；取走货物的顺序不影响计数。

输入格式

第一行包含两个正整数 $n,m$，分别表示货物数量和颜色种类数。

第二行包含 $n$ 个正整数 $c_1,c_2,\ldots,c_n$，其中 $c_i$ 表示第 $i$ 件货物的颜色。

输出格式

输出一个非负整数，表示满足要求的不同取法数量。

样例

5 3
1 2 2 1 3

2

3 3
2 1 3

1

样例解释

对于样例 $1$，满足要求的货物编号集合为 $\{1,2,5\}$ 和 $\{3,4,5\}$，共 $2$ 种。以 $\{1,2,5\}$ 为例，按编号 $1,2,5$ 或 $5,1,2$ 的顺序取走货物，均属于同一种取法。

对于样例 $2$，需要取走全部 $3$ 件货物，它们的颜色恰好各不相同。无论按什么顺序取走，最终取走的编号集合都是 $\{1,2,3\}$，因此只有 $1$ 种取法。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$
$1$	$20$	$20$
$2$	$30$	$2000$
$3$	$50$	$2\times 10^5$

对于 $100\%$ 的数据，$1\le m\le n\le 2\times 10^5$，$1\le c_i\le m$。