CF1582F2 Korney Korneevich and XOR (hard version)

Alex_Wei · 2021-10-28 14:32:16 · 题解

1582F2. Korney Korneevich and XOR (hard version)

看到题目一个基本的想法是设 f_{i,j} 表示是否存在以前 i 位以 j 结尾且异或和为 k 的子序列，这样做复杂度爆炸，是 nV^2 的（V=2^{13}-1\geq \max a_i），加上 bitset 优化可以通过 easy version。

实际上从前往后考虑的时候我们并不关心当前位置，因此实际有用的状态只有 V^2 个：以哪个数结尾，以及异或和是多少。

但是这个状态设计有些鸡肋，我们没办法优化。换个 DP 方法：设 f_{j,k} 表示是否存在以 <j 的数结尾且异或和为 k 的子序列。假设当前数为 a_i，那么枚举 k，若 f_{a_i,k}=1 则更新 f_{j,k\oplus a_i}\ (a_i<j\leq V)。实际上对于相同的 k\oplus a_i 我们并没有必要每次都从 a_i 枚举到 V 来更新，因为我们知道若 f_{j,k} 被更新为 1，所以任何 >j 的 j’ 的 f_{j',k} 也一定是 1，不需要继续增大下去了。因此，记录一个 mx_v 表示下一次遇到 k\oplus a_i=v 的时候应该从 a_i+1 枚举到 mx_v，然后用 a_i 更新 mx_v 即可。

此外，对于同一个 a_i 的 f_{a_i,k}，若 k 枚举过了就没有必要再枚举。故开一个桶 buc_{a_i} 记录 f_{a_i,k} 还没有被枚举过的 k 有哪些，遇到 a_i 就全部更新掉 k\oplus a_i 然后把 buc_{a_i} 清空。

复杂度分析：枚举复杂度：每个 buc_{a_i} 最多存在过 V 个数，共有 a_i 个这样的桶。更新复杂度：每个 v 的 mx_v 会从 V 枚举到 0，共有 V 个这样的 v。因此时间复杂度为 \mathcal{O}(n+V^2)。

const int V = 1 << 13;
int n, ans = 1, vis[V], mx[V];
vint buc[V];

int main() {
    cin >> n, vis[0] = 1;
    for(int i = 1; i < V; i++) buc[i].pb(0), mx[i] = V - 1;
    for(int i = 1; i <= n; i++) {
        int a = read();
        for(int it : buc[a]) {
            int p = it ^ a; ans += !vis[p], vis[p] = 1;
            while(mx[p] > a) buc[mx[p]--].pb(p); 
        } buc[a] = {};
    } cout << ans << endl;
    for(int i = 0; i < V; i++)
        if(vis[i]) cout << i << " ";
    cout << endl;
    return 0;
}