#BZOJ4286. 石中剑的考验
-
ID: 2883
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
石中剑的考验
No submission language available for this problem.
题目描述
小X最近看了亚瑟王的传说，幻想自己也能成为这样的传奇人物。在梦中，小X看到前方由近及远有n个高度互不相
同且均为整数的台阶，其中最矮的高度为1，最高的高度为n。小X隐约听见有人在说话：“拔出此石中剑者，即为
英格兰之王。”顺着声音的方向，小X看见了一把插在石缝中的装饰华美的剑。“莫非这就是……”小X跑过去，恨
不得立刻将其拔出。然而，小X接近它时就会被弹开。刚刚的声音再次响起：“看到那些台阶了吗？要想拔出石中
剑，首先要跨过那些台阶。你可以选择从任意一个台阶出发，每次向前跨越若干个台阶，但必须保证每次落脚的台
阶都高于上一次落脚的台阶。为了展现王的姿态，你要让落脚的次数尽量多。”这可难不倒小X，他轻松地完成了
任务，步伐在天空中划出了一道优美的弧线。“最后，你还要在心中默念一个数，才能得到石中剑的认可。记住自
己刚才的轨迹了吗？你看那些台阶，其实都是虚幻的，可以任意改变顺序。石中剑需要你回答的是，那些台阶有多
少种不同的排列方法，可以用你刚才的轨迹来完成之前的任务呢？”思考了许久，小X身上直冒汗。身为正义使者
的你，想要帮助他在梦中成为英格兰之王。为此，你潜入了他的意识，得到了他刚才的轨迹。现在，你必须尽快得
到答案，从而放入他的意识，使他通过石中剑的考验。
输入格式
第一行一个整数n。
第二行一个整数k，表示小X刚才轨迹落脚的次数。
第三行k个整数，表示这个轨迹依次落脚的台阶的高度。
1 ≤ n ≤ 15，答案小于 2^31
输出格式
第一行一个整数，表示答案
5
3
1 3 4
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)。