双子时空 (back.cpp\c\pas)
【问题描述】
你救出了小丁。
这激怒了双胞胎们。
他们祭出大招——“双子时空”。你和小丁分别被关在两个时空里,小丁的时空里有一个1到n的排列,他被要求给出这个排列的一个最长上升子序列;你的时空里可以看到小丁给出的最长上升子序列,你需要推断出原排列是什么。显然,可能有很多数列满足这个最长上升子序列,你想要知道这样的排列有多少,从而计算出自己答对的概率。
…………
【输入格式】
第1行一个正整数n;
第2行一个正整数k,表示最长上升子序列的长度;
第3行k个整数,表示这个最长上升子序列。
【输出格式】
一行一个整数,表示原排列的可能数。
【输入输出样例】
back.in
5
3
1 3 4
back.out
11
【样例解释】
11种排列分别为(1, 3, 2, 5, 4), (1, 3, 5, 2, 4), (1, 3, 5, 4, 2), (1, 5, 3, 2, 4), (1, 5, 3, 4, 2), (2, 1, 3, 5, 4), (2, 1, 5, 3, 4), (2, 5, 1, 3, 4), (5, 1, 3, 2, 4), (5, 1, 3, 4, 2), (5, 2, 1, 3, 4)。
【数据范围】
对于前30%的数据 n ≤ 8。
对于100%的数据1 ≤ k ≤ n ≤ 15。
数据有一定梯度。
信息
- 难度
- 10
- 分类
- (无)
- 标签
- 递交数
- 8
- 已通过
- 0
- 通过率
- 0%
- 被复制
- 1
- 上传者