AT_arc100_d.[ARC100F] Colorful Sequences

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定整数 $N$ 、 $K$ ，以及一个长度为 $M$ 的整数序列 $A$ 。

如果一个整数序列的每个元素都是 $1$ 到 $K$ 之间的整数，并且存在一个长度为 $K$ 的连续子序列，恰好包含 $1$ 到 $K$ 的每个整数各一次，则称该序列是“彩色”的。

请你统计所有长度为 $N$ 的彩色整数序列中，包含与 $A$ 完全相同的连续子序列的个数，并求这些个数的总和。由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

输入格式

输入以如下格式从标准输入读入。

$N$ $K$ $M$ $A_1$ $A_2$ $\ldots$ $A_M$

输出格式

请输出所有长度为 $N$ 的彩色整数序列中，包含与 $A$ 完全相同的连续子序列的个数的总和，对 $10^9+7$ 取模。

输入输出样例

输入#1
```
3 2 1
1
```
输出#1
```
9
```
输入#2
```
4 2 2
1 2
```
输出#2
```
12
```
输入#3
```
7 4 5
1 2 3 1 2
```
输出#3
```
17
```
输入#4
```
5 4 3
1 1 1
```
输出#4
```
0
```
输入#5
```
10 3 5
1 1 2 3 3
```
输出#5
```
1458
```
输入#6
```
25000 400 4
3 7 31 127
```
输出#6
```
923966268
```

输入#7

9954 310 12
267 193 278 294 6 63 86 166 157 193 168 43

输出#7

979180369

说明/提示

限制条件

$1 \leq N \leq 25000$
$1 \leq K \leq 400$
$1 \leq M \leq N$
$1 \leq A_i \leq K$
所有输入均为整数。

样例解释 1

长度为 $3$ 的彩色整数序列有 $(1,1,2)$ 、 $(1,2,1)$ 、 $(1,2,2)$ 、 $(2,1,1)$ 、 $(2,1,2)$ 、 $(2,2,1)$ 共 $6$ 个。对于这些序列，包含与 $A=(1)$ 完全相同的连续子序列的个数分别为 $2$ 、 $2$ 、 $1$ 、 $2$ 、 $1$ 、 $1$ 。因此，这些个数的总和为 $9$ ，即为答案。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页