1 条题解
-
0
题目分析
注意到题目要求我们计算合法排列的数量,不难想到进行排列 DP。
排列 DP 的常用套路是,设 表示将 或 插入序列时,符合某些条件的方案数。
于是我们设 表示将 插入序列时,最靠前的上升子序列的末尾位置为 时,符合条件的方案数。
为什么我们要这样设计状态呢?
假设一个序列为 ,当我们想要新加入一个数字 时,如果我们把这个数字插入在 的后面,由于 已经和之前的 分别构成了长度为 的上升子序列,因此插入在 的后面显然是不合法的。
也就是说,只要我们将一个新的数字插入在原本长度为 的上升子序列后,就一定是不合法的。
我们不难发现,想要让排列合法,就必须把新的数字填入到原本上升子序列末尾之前,所以要这样设计状态。
状态设计完,我们考虑怎么样转移。
转移分三种情况:
-
前 个构成了一个递减的序列时,此时序列中没有上升子序列,因此对于每个 ,我们都可以放置在后面并且产生一个上升的子序列,这个子序列就是排列中最靠前的子序列。因此,我们得出第一个转移方程。
-
我们新插入一个数字,插入到整个序列的最左边,此时不会对上升子序列数量与长度产生任何影响,但是由于插入到序列开头,因此所有原来末尾位置都会向后移动 ,方程直接累加方案数即可。
-
当我们把数字插入到除了序列最前面以外的合法位置,也就是位于最靠前上升子序列之前的位置时,最前的上升子序列末尾位置会变成插入的位置,我们外层枚举当前末尾位置 ,内层枚举下一个数字填入的位置 ,填入数字,即:
$f_{i+1,k} = f_{i+1,k} + f_{i,j} \ (j\in[2,i] ,k\in[2,j])$
到这里,我们的方程已经推完了,但我们注意到题目说的是最长上升子序列长度不超过 的排列方案数,因此还需要注意: 这种倒序的排列也是一种方案,因此答案应该是
记得在过程中及时取模(采用减法常数更小),最后输出答案即可。
优化
但是这个方程的复杂度为 ,不足以通过本题,因此我们需要考虑优化。
不难发现,在方程中需要增加的部分都是连续的,也就是一段区间加法,因此我们可以考虑进行差分,在每一层转移之后进行合并。
到这里,我们通过差分已经把时间复杂度从原本的 优化到了 。
我们还可以使用滚动数组优化这个 DP 的空间复杂度。
20pts
枚举所有解。
+30pts
注意到可能的 至多 种情况,枚举 对应的 和,时间复杂度为 。
+30pts
可能的 至多 对,类比之前的做法,时间复杂度为
100pts
首先我们把这题的 给去掉,那么我们按位算贡献,可以求出和。这是这种式子的通用套路。
考虑加上 ,那么我们先按照 的最高位分为:,,, 四种情况。
先考虑不同的情况,可以发现用贡献的不同的组如下:
-
贡献为 。
-
贡献为 。
-
贡献为 。
-
贡献为 。
-
以下几种可能最高位相同,无法通过最高位比较:
- 与
- 与
对于无法比较的两组,我们把两组合并起来,然后就变成了子问题,递归处理下一位。
再考虑相同的情况,发现同组内部贡献最高位一定为 ,因此可以划分成 个子问题继续递归下去。
每次考虑最高层,一共至多递归 层,时间复杂度为 。
-
- 1
信息
- ID
- 153
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者