Codeforces 1582F1. Korney Korneevich and XOR (easy version)

传送门

题目大意

一个长为 \(n(1\leq n\leq 10^5)\) 的序列，\(0\leq a_i\leq500\)，求出所有的 \(n\) 的上升子序列的不同的异或和，升序输出。

思路

考虑 \(dp\) ，设 \(f_{i,j}\) 为考虑前 \(i\) 个数字，异或和为 \(j\) 的上升子序列的最后一个数字的最小值。我们贪心的让异或和为 \(j\) 的每个上升子序列的最后一个数最小，这样后面就有更多可能的数能够异或进来，从而有更多可能的取值，因此转移显然为 \(f_{i,j\oplus a_i}=min(f_{i-1,j\oplus a_i},min_{a_i>f_{i-1,j}}\space\{a_i\})\) ，可以用滚动数组优化掉第一维，初始让 \(f_{0,0}=-1\) ，其余为 \(inf\) 即可，最后所有值不为 \(inf\) 的 \(f_{n,i}\) 的 \(i\) 即为答案。

代码

#include
#include
#include
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using PII = pair;
using TP = tuple;
#define all(x) x.begin(),x.end()
#define pb push_back
#define mk make_pair
//#define int LL
//#define lc p*2
//#define rc p*2+1
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
//#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 100010;

int N, A[maxn];
int f[2][550];

void solve()
{
	memset(f, inf, sizeof(f));
	f[0][0] = -1;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j <= 512; j++)
			f[i % 2][j] = f[(i - 1) % 2][j];
		for (int j = 0; j <= 512; j++)
		{
			if (A[i] > f[(i - 1) % 2][j])
				f[i % 2][j ^ A[i]] = min(f[i % 2][j ^ A[i]], A[i]);
		}
	}
	int cnt = 0;
	vectorans;
	for (int i = 0; i <= 512; i++)
	{
		if (f[N % 2][i] != inf)
			cnt++, ans.pb(i);
	}
	cout << cnt << endl;
	for (auto& c : ans)
		cout << c << ' ';
	cout << endl;
	cout << endl;
}

int main()
{
	IOS;
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> A[i];
	solve();

	return 0;
}