#A0109. 卡片左移
卡片左移
题目背景
小林把 张卡片从左到右排成一行,第 张卡片上写着整数 。不同的卡片可能写着相同的整数。
小林准备进行一次调整。他想知道,调整后,卡片上的数字从左到右可以组成多少种不同的序列。
题目描述
给定一个长度为 的整数序列 。你必须恰好进行一次以下操作:
选择两个下标 ,满足 ,将原来位于第 个位置的元素取出,插入到原来第 个元素的前面。也就是说,将序列变为
$$(a_1,\ldots,a_{l-1},a_r,a_l,a_{l+1},\ldots,a_{r-1},a_{r+1},\ldots,a_n)。$$当 时,规定序列保持不变。其余元素的相对顺序不变。
求通过一次上述操作,可以得到多少种不同的数字序列。
两个结果不同,当且仅当存在某个位置,它们在该位置上的数字不同。即使选择的下标不同,只要最后得到的数字序列相同,就只能计算一次。
输入格式
从标准输入读入数据。
第一行包含一个整数 。
第二行包含 个整数 ,相邻整数之间用一个空格隔开。
输出格式
向标准输出输出一个整数,表示不同结果的数量。
答案不需要取模。请注意答案可能超出 32 位有符号整数的表示范围。
样例
3
1 2 1
3
解释
可以得到且仅能得到以下三种序列:
- :选择 ;
- :选择 ;
- :选择 。
选择 也会得到 ,因此不应重复计数。
5
1 1 1 1 1
1
解释
无论选择哪两个合法下标,得到的数字序列都相同。
6
1 4 1 4 2 1
12
30
24 22 18 20 14 22 14 14 26 14 26 26 20 22 24 18 22 22 14 24 18 14 14 24 22 18 18 26 14 20
30
24 22 18 20 14 22 14 14 26 14 26 26 20 22 24 18 22 22 14 24 18 14 14 24 22 18 18 26 14 20
数据范围与子任务
对于所有测试数据,保证:
- ;
- ;
- 所有输入均为整数。
本题采用子任务捆绑测试:只有通过某个子任务中的全部测试点,才能获得该子任务的全部分数。
| 子任务编号 | 分值 | 的上限 | 额外性质 |
|---|---|---|---|
| 1 | 10 | 无 | |
| 2 | 15 | ||
| 3 | 20 | ||
| 4 | 10 | 所有 两两不同 | |
| 5 | 15 | ||
| 6 | 30 | 无 |