题意：给出一个序列 \(a\)，每次可以将一项 \(a_i\) 变成 \(a_i\oplus a_{i-1}\)，问 \(a\) 序列的最长上升子序列最大为多少。\(n\le 10^6,V< 2^{60}\)
做法：
首先稍微手玩一下会发现 \(a_i\) 可以随意异或上前面的任意一个数，这个从前往后推一下就行。同时考虑从后往前满足每一个数，所以每个数选什么是独立的。
那么就是考虑每个数可以变成 \(a_i\) 任意异或上前面的数，异或出来的序列上升子序列最大长度。
既然是随意异或上前面每个数，那么我们可以先对每个前缀求一个线性基。为了方便，我们先把所有的基去消个元，这样就可以用一个二进制数去对应一个实际的数，并且这两个的大小关系是完全一样的，就比较方便我们去比较。
考虑有两种求上升子序列的做法，一种是直接枚举第 \(i\) 个然后对前面取 \(\max\)，但是有个问题是我每个位置取值是很多的，直接枚举爆炸完了。所以我们采用另一种做法，考虑 \(dp_i\) 代表长为 \(i\) 的上升序列末尾最小值为多少。
对两类情况分别讨论，假设目前线性基大小为 \(k\)，一种是我 \(a_i\) 加入线性基之后不改变线性基，那么很显然 \([0,2^k)\) 都是可以凑出来的，转移为 \(f_{i}\leftarrow f_{i-1}+1\)。我们可以把连续线性基大小都为 \(k\) 的一起做，转移改为 \(f_{i}\leftarrow f_{i-k}+k\)。但是要注意，不能大于等于 \(2^k\)，因为填不了这么大。
那么考虑第二种，改变线性基的情况，这种情况只有 \(O(\log V)\) 种，所以我们可以接受 \(O(n)\) 的处理。我们先把 \(dp\) 值更新成加入这个数之后的状态，具体可以见代码。然后考虑 \(dp_i\) 怎么贡献，那就是找到 \(dp_i\) 后第一个比 \(dp_i\) 大且包含我新加入的这一位的元素即可。
剩下就是一些代码层面上的东西，可以看代码理解一下具体的过程。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5;
int n, a[maxn];
struct Base {int d[61];pair<int, int> ins(int x) {int msk = 0;for (int i = 60; i >= 0; i--) {if((x >> i) & 1) {if(!d[i]) {d[i] = x;for (int j = i - 1; j >= 0; j--)if(d[j] && ((d[i] >> j) & 1))d[i] ^= d[j];for (int j = 60; j >= i + 1; j--) {if(d[j]) {msk <<= 1;if((d[j] >> i) & 1)d[j] ^= d[i], msk |= 1;}}msk <<= 1;return make_pair(i, msk);}x ^= d[i];}}return make_pair(-1, 0);}
} Tree;
int dp[maxn], len, mx;
void shift(int x) {len += x;for (int i = len; i > x; i--)dp[i] = dp[i - x] + x;for (int j = 1; j <= x; j++)dp[j] = j - 1;while(dp[len] >= (1ll << mx))len--;
}
int cal(int x) {int cnt = 0;while(x)cnt ^= x & 1, x >>= 1;return cnt;
}
signed main() {ios::sync_with_stdio(false);cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];int lst = 0;for (int i = 1; i <= n; i++) {// cout << Tree.d[0] << endl;pair<int, int> mp = Tree.ins(a[i]);if(mp.first == -1) {lst++;continue;}shift(lst), lst = 0;mx++;int ct = 0;for (int j = 0; j < mp.first; j++)ct += (Tree.d[j] > 0);int nw = mp.second; nw |= 1; nw <<= ct;for (int j = 1; j <= len; j++) {dp[j] += (dp[j] >> ct) << ct;if(cal(nw & dp[j]))dp[j] |= (1ll << ct);}// cout << nw << " asdf" << cal(1 & nw) << " " << ct << " " << mp.first << endl;for (int j = len; j >= 0; j--) {int val = dp[j] + 1;// cout << val << " " << (nw & val) << " " << j << " " << nw << endl;while(!cal(nw & val))val = ((val >> ct) + 1) << ct;if(val >= (1ll << mx))continue;if(j == len)dp[++len] = 9e18;dp[j + 1] = min(dp[j + 1], val);}
// for (int j = 0; j <= len; j++)
// cout << dp[j] << " ";
// cout << endl;}shift(lst);cout << len << endl;return 0;
}