2025-08-10 21:12 门头沟学院 发布于广东省
关注
牛客周赛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次方 ，则采用快速幂解决。
全部评论
相关推荐
牛客公司氛围 254人发布