#P16346. [2026年山东第二轮集训]数数题
[2026年山东第二轮集训]数数题
题目描述
给定长度为 的整数序列
你可以进行任意次(也可以是 次)以下操作:
- 选择一个区间 ;
- 计算
- 对所有 ,令
设经过若干次操作后最终得到整数序列 。求一共有多少种不同的序列 ,答案对 取模。
输入格式
第一行一个整数 。
第二行 个整数 。
输出格式
输出一行一个整数,表示可能得到的不同序列 的数量对 取模后的结果。
样例
样例 1
输入
4
1 3 4 2
输出
10
数据范围
子任务
| 子任务编号 | 特殊性质 | 分值 | |
|---|---|---|---|
| 1 | 无 | 10 | |
| 2 | AB | ||
| 3 | B | ||
| 4 | A | ||
| 5 | 无 | ||
| 6 | A | ||
| 7 | 无 | ||
| 8 | A | ||
| 9 | 无 | 20 |
特殊性质:
- A: 是一个排列;
- B: 单调不降。