有多少集合 \(S\)，每个元素都在 \([0, 2 ^ N)\) 之间，且所有偶数大小的子集的异或和不为 \(0\)。
奇数大小的子集 \(\oplus\) 和可以为 \(0\)，可是如果有 \(\ge 2\) 个不空且不相同的奇子集 \(S, T\) \(\oplus\) 和都为 \(0\)，\(S \oplus T\) 是个偶子集，则其 \(\oplus\) 和是 \(0\)。
如果没有这个奇偶的限制，则根据线性基的性质，答案就是
\[\sum_{i = 0} ^ n \frac{1}{i!} \prod_{j = 0} ^ {i - 1} (2 ^ n - 2 ^ j) \]否则 DP，设 \(f(i, t = 0 / 1)\) 表示当前已经放到了第 \(i\) 个数，\(t\) 表示是否已经有奇子集 \(\oplus\) 和为 \(0\)。\(f(i, 0)\) 到 \(f(i + 1, 1)\) 就选前 \(i\) 个数理的线性基已经能凑出来的数。有 \(2 ^ i\) 种，但是只有 \(2 ^ {i - 1}\) 满足“奇数大小”要求。具体可以看代码。
void solveT() {
cin >> n;
vector<int> f = {1, 0};
int res = 1;
R(i, 1, n + 2) {
if (i == 1) f[1] = 1;
else f[1] = add(mul(f[1], add(p2[n], mod - p2[i - 2])), mul(f[0], p2[i - 2]));
f[0] = mul(f[0], add(p2[n], mod - p2[i - 1]));
res = add(res, mul(add(f[1], f[0]), ifac[i]));
}
cout << res ntr;
}