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;
}