CF1582F2 Korney Korneevich and XOR (hard version) 题解

题目链接：Korney Korneevich and XOR (hard version)

题意：

给一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$ ，寻找在 $a$ 的所有递增子序列（可以为空）的异或和中出现的数。

输入格式：

第一行一个正整数 $n$ 表示序列长度。

第二行 $n$ 个整数表示序列 $a$ 。

输出格式：

从小到大输出在 $a$ 的所有子序列（可以为空）的异或和中出现的数。

数据范围：

$1\le n\le10^6,0\le a_i\le5000$ 。

注意到值域 $V \le 5000$ ，这个范围可以 $\mathcal{O}(V^2)$ 。

考虑设 $f_{j,k}$ 表示是否存在结尾小于 $j$ 且异或和为 $k$ 的子序列。

设当前枚举的数为 $a_i(a_i < j \le V)$ ，转移方程为

$f_{j, k\oplus a_i} = \left[\sum[f_{a_i,k}] > 1\right]$

这个式子对应代码就是 f[j][k ^ a[i]] |= f[a[i]][k] 。

实际上，对于相同的 $k \oplus a_i$ ，我们无需每次都将 $j$ 从 $a_i$ 枚举到 $V$ 转移。

因为当 $f_{j,k}$ 被更新为 $\mathtt{Ture}$ 时，显然任何大于 $j$ 的位置 $l$ 有 $f_{l,k}=\mathtt{Ture}$ 。

所以我们可以记录一个 mx[v] 表示下次遇到 $v=k\oplus a_i$ 时只需枚举到 mx[v] ，接着用 $a_i$ 更新 mx[v] 。

另外，由于同一个 $a_i$ 的 $f_{a_i,k}$ ，如果 $k$ 枚举过就无需再枚举了（它的答案已经被记录在 $f_{j,k\oplus a_i}$ 中了）。

所以我们可以直接开一个 vector 记录每个 $a_i$ 有哪些 $k$ 没有被枚举

每新加入一个 $a_i$ ，就把 $a_i$ 存在的 $k$ 全部去更新 $k\oplus a_i$ ，并清空 $a_i$ 的桶，这样 vector 中至多存在 $V$ 个数。

时间复杂度 $\mathcal{O}(n+V^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }

const int V = 1 << 13;
vector<int> vec[V];
int n, res = 1, mx[V]; char vis[V];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; vis[0] = true;
    for(int i = 1; i < V; i++) { vec[i].push_back(0), mx[i] = V - 1; }
    for(int i = 1, x; i <= n; i++)
    {
        cin >> x;
        for(int k : vec[x])
        {
            int p = k ^ x; res += (!vis[p]); vis[p] = true;
            while(mx[p] > x) vec[mx[p]--].push_back(p);
        }
        vec[x].clear();
    }
    cout << res << '\n';
    for(int i = 0; i < V; i++) if(vis[i]) cout << i << ' ';
    return 0;
}