牛客周赛103C
题意:给你一个整数n为排列长度,问你能组成多少种不同的排列方案是好数组,其中好数组的定义为当且仅当该排列满足恰好存在 n 个子区间是一个排列。
思路
由于一个长度为 𝑘的排列必须包含 1∼𝑘的所有元素,所以题意可以转化成对于序列 1,2,3,⋯⋯,n 的任意前缀都需要连续放置。
初始序列只有 1 这个元素,对于 𝑖∈[2,𝑛],我们可以考虑放在序列的首部或者尾部,有 2 种选择,根据乘法原理,答案便是 2𝑛−1 种, 𝑛≦10的9次方 ,则采用快速幂解决。
思路
由于一个长度为 𝑘的排列必须包含 1∼𝑘的所有元素,所以题意可以转化成对于序列 1,2,3,⋯⋯,n 的任意前缀都需要连续放置。
初始序列只有 1 这个元素,对于 𝑖∈[2,𝑛],我们可以考虑放在序列的首部或者尾部,有 2 种选择,根据乘法原理,答案便是 2𝑛−1 种, 𝑛≦10的9次方 ,则采用快速幂解决。
全部评论
相关推荐
查看7道真题和解析 点赞 评论 收藏
分享
点赞 评论 收藏
分享
02-25 17:58
吉首大学张家界学院 Python
最喜欢秋天的火龙果很...:第一份工作一定要往大的去,工资低点没事。后面换工作会更好找,即使你去小公司,你也不可能不会换工作的。所以找大的去 点赞 评论 收藏
分享
查看23道真题和解析 点赞 评论 收藏
分享
