1 条题解

  • 0
    @ 2026-11-15 17:55:00

    题目分析

    注意到题目要求我们计算合法排列的数量,不难想到进行排列 DP。

    排列 DP 的常用套路是,设 fi,∗f_{i,*} 表示将 [1,i][1,i] 或 [i,n][i,n] 插入序列时,符合某些条件的方案数。

    于是我们设 fi,jf_{i,j} 表示将 [1,i][1,i] 插入序列时,最靠前的上升子序列的末尾位置为 jj 时,符合条件的方案数。

    为什么我们要这样设计状态呢?

    假设一个序列为 3,2,1,4,53,2,1,4,5 ,当我们想要新加入一个数字 66 时,如果我们把这个数字插入在 44 的后面,由于 44 已经和之前的 3,2,13,2,1 分别构成了长度为 22 的上升子序列,因此插入在 44 的后面显然是不合法的。

    也就是说,只要我们将一个新的数字插入在原本长度为 22 的上升子序列后,就一定是不合法的。

    我们不难发现,想要让排列合法,就必须把新的数字填入到原本上升子序列末尾之前,所以要这样设计状态。

    状态设计完,我们考虑怎么样转移。

    转移分三种情况:

    • 前 ii 个构成了一个递减的序列时,此时序列中没有上升子序列,因此对于每个 j∈[2,i+1]j\in[2,i + 1],我们都可以放置在后面并且产生一个上升的子序列,这个子序列就是排列中最靠前的子序列。因此,我们得出第一个转移方程。

      fi+1,j=fi+1,j+1 (j∈[2,i+1])f_{i+1,j} = f_{i+1,j} + 1 \ (j\in[2,i + 1])

    • 我们新插入一个数字,插入到整个序列的最左边,此时不会对上升子序列数量与长度产生任何影响,但是由于插入到序列开头,因此所有原来末尾位置都会向后移动 11,方程直接累加方案数即可。

      fi+1,j+1=fi+1,j+1+fi,j (j∈[2,i])f_{i+1,j+1} = f_{i+1,j+1} + f_{i,j} \ (j\in[2,i])

    • 当我们把数字插入到除了序列最前面以外的合法位置,也就是位于最靠前上升子序列之前的位置时,最前的上升子序列末尾位置会变成插入的位置,我们外层枚举当前末尾位置 j∈[2,i]j\in[2,i] ,内层枚举下一个数字填入的位置 k∈[2,j]k\in[2,j] ,填入数字,即:

      $f_{i+1,k} = f_{i+1,k} + f_{i,j} \ (j\in[2,i] ,k\in[2,j])$

    到这里,我们的方程已经推完了,但我们注意到题目说的是最长上升子序列长度不超过 22 的排列方案数,因此还需要注意:n,n−1,n−2…2,1n,n - 1,n-2 … 2,1 这种倒序的排列也是一种方案,因此答案应该是

    1+∑i=2nfn,i1 + \sum_{i=2}^{n}f_{n,i}

    记得在过程中及时取模(采用减法常数更小),最后输出答案即可。


    优化

    但是这个方程的复杂度为 O(n3)O(n^3) ,不足以通过本题,因此我们需要考虑优化。

    不难发现,在方程中需要增加的部分都是连续的,也就是一段区间加法,因此我们可以考虑进行差分,在每一层转移之后进行合并。

    到这里,我们通过差分已经把时间复杂度从原本的 O(n3)O(n^3) 优化到了 O(n2)O(n^2)。

    我们还可以使用滚动数组优化这个 DP 的空间复杂度。

    20pts

    O(n2)O(n^2) 枚举所有解。

    +30pts

    注意到可能的 (ai,bi)(a_i,b_i) 至多 O(V2)O(V^2) 种情况,枚举 i,ji,j 对应的 (ai,bi)(a_i,b_i) 和(aj,bj)(a_j,b_j),时间复杂度为 O(V4)O(V^4)。

    +30pts

    可能的 (ai,bi)(a_i,b_i) 至多 O(log⁡2V)O(\log^2 V) 对,类比之前的做法,时间复杂度为 O(log⁡4V)O(\log^4 V)

    100pts

    首先我们把这题的 min⁡\min 给去掉,那么我们按位算贡献,可以求出和。这是这种式子的通用套路。

    考虑加上 min⁡\min,那么我们先按照 (ai,bi)(a_i,b_i) 的最高位分为:(1,0)(1,0),(0,1)(0,1),(1,1)(1,1),(0,0)(0,0)​ 四种情况。

    先考虑不同的情况,可以发现用贡献的不同的组如下:

    • (0,0),(0,1)(0,0),(0,1) 贡献为 ai⊕aja_i⊕a_j。

    • (0,0),(1,0)(0,0),(1,0) 贡献为 bi⊕bjb_i⊕b_j。

    • (1,1),(1,0)(1,1),(1,0) 贡献为 ai⊕aja_i⊕a_j。

    • (1,1),(0,1)(1,1),(0,1) 贡献为 bi⊕bjb_i⊕b_j。

    • 以下几种可能最高位相同,无法通过最高位比较:

      • (0,0)(0,0) 与 (1,1)(1,1)
      • (0,1)(0,1) 与 (1,0)(1,0)

    对于无法比较的两组,我们把两组合并起来,然后就变成了子问题,递归处理下一位。

    再考虑相同的情况,发现同组内部贡献最高位一定为 00,因此可以划分成 44 个子问题继续递归下去。

    每次考虑最高层,一共至多递归 O(log⁡V)O(\log V) 层,时间复杂度为 O(nlog⁡2V)O(n \log ^2V)。

    • 1

    信息

    ID
    153
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者