1 条题解

  • 0
    @ 2026-11-15 16:40:00

    30pts

    2N2^N 枚举所有情况进行判定,时间复杂度为 O(2N)O(2^N)

    +30pts

    对于 0≤ai≤30 \leq a_i \leq 3,f[i][j][k]f[i][j][k] 表示考虑了序列的前 ii 个数,其中 AA 集合中所有元素的或运算为 jj,BB 集合中所有元素的或运算为 kk 的方案数,其中 j,k∈[0,3]j,k \in [0,3],背包进行转移,时间复杂度为 O(N)O(N)。

    100pts

    对于二进制下某一位 kk,若满足第 kk 位上为 11 的 aia_i 个数不为 00 个,那么所有第 kk 位上为 11 的数不能划分在同一个集合。

    例如对于 {(101)2,(100)2,(001)2,(111)2}\{(101)_2,(100)_2,(001)_2,(111)_2 \} 这三个数,{(101)2,(001)2,(111)2}\{(101)_2,(001)_2,(111)_2\} 一定不能被划分在同一个集合,否则另一个集合的最低位一定为 00,不满足题设条件。

    所有第 kk 位上为 11 的数不能划分在同一个集合并不好处理,我们考虑其相反面进行容斥,所有第 kk 位上为 11 的数都应当划分在同一个集合并不好处理

    考虑容斥,强制钦定第 kk 位上为 11 的数划分在同一个集合。

    现在有若干数强制钦定在同一个集合,将这些数用并查集连接,在同一个并查集里的数说明一定要被分配在一个集合里,考虑乘法原理,每个并查集的联通块都有 22 种可能,即划分在 AA 或 BB ,那么方案数即为 2并查集联通块个数2^{并查集联通块个数},

    容斥一共有 O(215)O(2^{15}) 种情况。

    对于每一种情况,需要进行 O(15×N)O(15 \times N) 的判断,但所有数最多合并到同一个并查集里,并查集部分的复杂度为N×α(N)N \times \alpha(N),复杂度为O(215×(15×N+N×α(N)))O(2^{15} \times (15\times N +N \times \alpha(N)))。

    • 1

    信息

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