Upd on 2022.4.3 修改错误。

P3447 [POI2006]KRY-Crystals

POI 合集。

读完题目，纷繁复杂的限制让我们无从下手。从哪个条件作为突破口呢？肯定是最严格的异或限制。

异或有性质 $a \oplus b = c\Rightarrow b = a\oplus c$。对应到题目中，就是若序列 $a$ 有 $n - 1$ 个数确定，则未定数只能等于所有确定数的异或和。这启发我们思考，有没有一种可能，未定数对应的限制 $m_i$ 非常大，以至于无论 $n - 1$ 个数怎么选，它们的异或和总不大于 $m_i$，这样我们就可以很方便地用乘法原理求出答案。

实际上有可能！考虑第 $i$ 位，假设存在 $p$ 使得 $m_p$ 这一位为 $1$，但 $a_p$ 为 $0$，说明若所有数字在第 $i$ 位及其高位异或和为 $0$，那么无论其它数字低 $i - 1$ 位怎么填都符合条件，因为 $a_p$ 在第 $i$ 位小于 $m_p$，所以接下来的低 $i - 1$ 位没有限制。

这启发我们直接枚举所有 $a_p$ 与 $m_p$ 的最短 LCP，即 存在 $p$ 使得 $m_p$ 在第 $i$ 位为 $1$ 但 $a_p$ 为 $0$，且 $a$ 高于第 $i$ 位的部分与 $m$ 相同 的位数 $i$。这样，我们只需把任意一个 $p$ 的系数变为 $1$（因为它依赖于剩余数的异或和），剩下的系数用乘法原理乘起来即可。

具体地，考虑我们关心什么：第 $i$ 位异或和为 $0$ 且存在 $p$。这启发我们设计 DP $f_{j, k, l}$ 表示考虑到第 $j$ 个数，第 $i$ 位异或和为 $k$ 且是否存在 $p$。根据乘法原理与实际意义转移：

若 $m_j$ 第 $i$ 位为 $1$，那么 $a_j$ 可以选择 $0 / 1$：选 $0$ 的方案数为 $2^i$，选 $1$ 的方案数为 $m_j$ 在低 $2 ^ {i - 1}$ 位的值加上 $1$，记作 $c_i$，实际上就是 $(m_j \& (2 ^ i - 1)) + 1$。从 $l = 0$ 转移到 $l = 1$ 时，系数为 $1$，表示钦定 $j$ 的系数为 $1$。

$$\begin{aligned} & f_{j, 0, 0} = f_{j - 1, 1, 0}\times c_j \\ & f_{j, 1, 0} = f_{j - 1, 0, 0}\times c_j \\ & f_{j, 0, 1} = f_{j - 1, 1, 1}\times c_j + f_{j - 1, 0, 1}\times 2 ^ i + f_{j - 1, 0, 0} \\ & f_{j, 1, 1} = f_{j - 1, 0, 1}\times c_j + f_{j - 1, 1, 1}\times 2 ^ i + f_{j - 1, 1, 0} \end{aligned}$$

若 $m_j$ 第 $i$ 位为 $0$，则只能选 $0$ 且方案数为 $c_j$。

$$f_{j, k, l} = f_{j - 1, k, l}\times c_j$$

最后，若 $m$ 比 $i$ 高的位的异或和为 $0$ 才能计算当前位贡献 $f_{n, 0, 1}$，因为钦定了高位 $a$ 都取 $m$。注意全零序列会被统计到，因此最后答案减 $1$。时间复杂度是优秀的 $\mathcal{O}(n\log m)$。

总结一下，对于位运算相关 有限制 的计数题，首先考虑 最严格 的限制，并尽量 独立每一位，如果做不到就按顺序考虑每一位的限制。选择本题的原因是希望各位同学能够感受到这种按位枚举什么东西然后再 DP 的套路。

#include <bits/stdc++.h>
using namespace std;
const int N = 50 + 5;
unsigned long long n, ans, xs, m[N], f[2][2][2];
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) scanf("%llu", &m[i]), xs ^= m[i];
	ans = !xs, xs = 0;
	for(int i = 31; i >= 0; i--) {
		memset(f, 0, sizeof(f)), f[0][0][0] = 1;
		for(int j = 1, p = 0, q = 1; j <= n; j++, swap(p, q)) {
			unsigned long long coef = (m[j] & ((1 << i) - 1)) + 1;
			xs ^= m[j] >> i + 1;
			for(int c : {0, 1}) for(int d : {0, 1}) f[q][c ^ m[j] >> i & 1][d] = f[p][c][d] * coef;
			if(m[j] >> i & 1) for(int c : {0, 1}) f[q][c][1] += (f[p][c][1] << i) + f[p][c][0];
		}
		if(!xs) ans += f[n & 1][0][1];
		else break;
	}
	cout << ans - 1 << endl;
	return 0;
}