P4869 albus就是要第一个出场

Problem

将一个大小为 \(n\) 集合的所有子集异或和排序（定义空集的异或和为 \(0\)；结果不去重），问某个数 \(x\) 的排名。

Solution

记线性基为 \(S\)。由于允许空集，则线性基能表示出的数有 \(2^{|S|}\) 个，且次数均为 \(2^{n - |S|}\)（考虑线性基外的 \(2^{n - |S|}\) 个异或和，每一个都能在线性基内唯一表示）。

然后只需求出在 \(\mathrm{span(S)} \cup \{ 0 \}\) 中比 \(x\) 小的数的个数 \(w\)，答案即为 \(2^{n - |S|}w + 1\)。

现在的问题是如何求出 \(w\)。

我们先思考一个类似的问题：求线性基张成空间中的第 \(k\) 小元素。其实把自由位按顺序排列，\(k\) 在自由位上的二进制表示对应的线性组合即为答案。

比如如果一组线性基为 10010、01000、00010，则其张成空间中的第 \(3\) 小元素（011）相当于使得右起第 \(1\) 位、第 \(3\) 位为 \(1\)、第 \(4\) 位为 \(0\) 的线性组合（从 \(0\) 开始），第 \(5\) 小元素（101）相当于使得右起第 \(1\) 位为 \(1\)、第 \(3\) 位为 \(0\)、第 \(4\) 位为 \(1\) 的线性组合（从 \(0\) 开始）。

正确性可以从最高自由位开始考虑，其为 \(1\) 的线性组合代表的元素一定比其为 \(0\) 的线性组合代表的元素值更大，以此类推，发现这就等价于排名在自由位上的二进制表示，容易证明自由位的二进制状态唯一对应一个线性组合。但注意，自由位的二进制状态并不等价于组合系数的二进制表示！后者需要按最高位从大到小的顺序确定基元素的组合系数。

然后再用类似地思想去解决原问题。这里我们的解决思路是：从高位向低位尽可能用线性基中的元素表示出 \(x\)。

将 \(x\) 在二进制下从高位向低位考虑，同时维护值 \(y\) 表示考虑 \(x\) 的高若干位时选取线性基中的某些元素进行异或的结果。初始化 \(y = 0\)。

若在某一非自由位上 \(x\) 与 \(y\) 不同，则不用再考虑之后的自由位，因为之后的自由位一定不会影响到当前位的大小判定。比较该位 \(x, y\) 的大小，如果在该位上 \(x\) 位 \(1\) 而 \(y\) 为 \(0\)，则将 \(w\) 加上 \(2^{c}\)（\(c\) 表示当前位及更低位上的自由位个数），然后返回答案。否则直接返回答案。

若当前位为自由位，考察 \(x\) 与 \(y\) 在该位上是否相同，如果不同就让 \(y\) 异或该位上的基元素。如果 \(x\) 在该位上为 \(1\)，使 \(w\) 加上 \(2^{c - 1}\)（\(c\) 表示当前位及更低位上的自由位个数，\(2^{c - 1}\) 相当于加上了钦定该位为 \(0\) 的元素个数）。

这样就可以得到 \(w\) 了。

值得一提的是，如果将所有位都遍历完了，但都没有退出，则最后一定有 \(x = y\)，且 \(y\) 是线性基的一个自由组合。

// Sea, You & Me
const int F = 31;
int qwq[F];
struct Linear_Base
{
	int b[F];
	int insert(int x)
	{
		for(int i = F - 1; i >= 0; --i)
			if(x & (1 << i))
			{
				if(b[i]) x ^= b[i];
				else return b[i] = x, 1;
			}
		return 0;
	}	
	int get(int x) // the num < x (including 0)
	{
		int sum[F];
		sum[0] = (b[0] != 0);
		for(int i = 1; i < F; ++i)
			sum[i] = sum[i - 1] + (b[i] != 0);
		int res = 0, y = 0;
		for(int i = F - 1; i >= 0; --i)
		{
			int _x = (x >> i) & 1;
			int _y = (y >> i) & 1;
			if(!b[i])
			{
				if(_x ^ _y)
				{
					if(_x > _y)
						res += qwq[sum[i]];
					break;	
				}	
			} 
			else
			{
				if(_x ^ _y) y ^= b[i];
				if(_x == 1) res += qwq[sum[i] - 1];
			}
		}
		return res;
	}
}L;
int n;
int main()
{
	qwq[0] = 1;
	for(int i = 1; i < F; ++i)
		qwq[i] = mul(qwq[i - 1], 2);
	read(n);
	int cnt = 0;
	for(int i = 1; i <= n; ++i)
	{
		int x; read(x);
		cnt += L.insert(x);		
	}
	int x; read(x);
	int res = L.get(x);
	res = inc(mul(res % MOD, qwqmi(2, n - cnt)), 1);
	printf("%d\n", res);
	return 0;
}