F1. Korney Korneevich and XOR (easy version)

题意

给定长度为n的序列a[n]，对于a[n]中的任意上升子序列(不连续)，其XOR值都加入答案的集合中，求这个答案集合。

首先，任意两个$a,b\le 512a,\; b\; \backslash le\; 512$ ，$a⨁b\le 512a\; \backslash bigoplus\; b\; \backslash le\; 512$，这样最后答案的集合大小不会超过512，这提示我们可能是一个$f(1e5,512)f(1e5,\; 512)$ 的DP. 设状态方程为 $f(i,j)f(i,\; j)$表示前$ii$个元素中，异或值为$jj$的序列的末位元素最小值。于是得到状态转移方程：

$f(i,j⨁a[i])=f(i-1,j⨁a[i])f(i,j\; \backslash bigoplus\; a[i])=f(i-1,j\; \backslash bigoplus\; a[i])$

若$a[i]\ge ja[i]\; \backslash ge\; j$，有$f(i,j⨁a[i])=min(f(i-1,j⨁a[i]),a[i])f(i,j\; \backslash bigoplus\; a[i])=min(f(i-1,j\; \backslash bigoplus\; a[i]),\; a[i])$

这个方程可以优化成一维，且不影响正确性

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int f[N];
int main() {
    int n; cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    memset(f, 0x3f, sizeof f); f[0] = 0;
    for(int i = 1; i <= n; i ++) {
        for(int j = 0; j < 512; j ++) {
            if(f[j] < a[i]) {
                f[j ^ a[i]] = min(f[j ^ a[i]], a[i]);
            }
        }
    }
    vector<int> ans;
    for(int i = 0; i < 512; i ++) {
        if(f[i] != 0x3f3f3f3f) ans.push_back(i);
    }
    cout << ans.size() << endl;
    for(auto &it: ans) cout << it << ' ';
}