START203——Subsequences of Subsequences（如何求偶数长度子序列的异或和的最大值） · znzryb
## 思路讲解
遇到这种题目不要慌，首先不难发现是线性基。
接着我们不要一下子想特别复杂的情况，我们就想一想 K=2 的时候是怎么样的？
// 因为两段不同的段，相互遮盖的长度是一样的。
// 奇数加奇数是偶数，偶数加偶数还是偶数
// 遮盖以后都是加减偶数，并不会影响段的长度的奇偶性。
这里用到了一个小技巧
就是这个我们知道，如果说我们只要求偶数长度子序列的
异或最大值怎么办呢？
这个时候可以给加入线性基的数字加一个标记，如果最后这个值有标记
就说明是奇数长度子序列得到的和
否则就是偶数长度子序列得到的和。
## AC代码
[https://www.codechef.com/viewsolution/1190285113](https://www.codechef.com/viewsolution/1190285113)
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) {
cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
cerr << "[ ";
for (T i : v) _print(i), cerr << " ";
cerr << "]";
}
template<typename T> void _print(set<T> s) {
cerr << "{ ";
for (T i : s) _print(i), cerr << " ";
cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
cerr << "{";
_print(p.first);
cerr << ", ";
_print(p.second);
cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
cerr << "{ ";
for (auto &p : m) _print(p), cerr << " ";
cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif
using ll = long long; using ull = unsigned long long;
using ld = double; using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>; using plb = pair<ll, bool>;
using pll = pair<ll, ll>; using vll = vector<ll>; using vb = vector<bool>;
using tll = tuple<ll, ll, ll>; using vii = vector<int>;
using vpll = vector<pll>; using vtll = vector<tll>;
using vdb = vector<ld>; using vc = vector<char>;
using arr3 = array<ll, 3> ; using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9+7; // 998244353;
static constexpr double eps = 1e-8; const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;
inline void __();
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> lT;
while (lT--)
__();
return 0;
}
/*
直接模拟肯定不行吗？
用 python 不难得出该结论
*/
vll base;
void add(ll x) {
FOR(i, 0, SZ(base) -1) {
x = min(x, x ^ base[i]);
}
if (x != 0) base.PB(x);
}
ll count() {
ll res = 1ll << SZ(base);
return res;
}
inline void __() {
cin >> N >> K;
vll A(N + 5);
base.clear();
// 这边需要特判一下。
if (N == K) {
ll res = 0;
FOR(i, 1, N) {
cin >> A[i];
res ^= A[i];
}
if (res == 0) {
cout << 1 << "\n";
} else {
cout << 2 << "\n";
}
return;
}
// 因为两段不同的段，相互遮盖的长度是一样的。
// 奇数加奇数是偶数，偶数加偶数还是偶数
// 遮盖以后都是加减偶数，并不会影响段的长度的奇偶性。
if (K & 1) {
FOR(i, 1, N) {
cin >> A[i];
add(A[i]);
}
cout << count() << "\n";
} else {
/*
这里用到了一个小技巧
就是这个我们知道，如果说我们只要求偶数长度子序列的
异或最大值怎么办呢？
这个时候可以给加入线性基的数字加一个标记，如果最后这个值有标记
就说明是奇数长度子序列得到的和
否则就是偶数长度子序列得到的和。
*/
ll flag = 1ll << 31;
FOR(i, 1, N) {
cin >> A[i];
add(A[i]^flag);
}
ll res = 1ll << (SZ(base) -1);
// reduced row echelon form （RREF）
// 我们利用阶梯型行列式REF的性质
// 只会出现一个含有flag 的数字，因此剪掉就行了。
cout << res << "\n";
}
}
/*
AC
https://www.codechef.com/viewsolution/1190285113
1
4 1
1 2 4 8
1
3 3
0 0 0
1
1 1
0
*/
```
:::
## 心路历程（WA，TLE，MLE……）