给定各数上限，求满足W XOR X XOR Y XOR Z=0的无序四元组数量

问题描述 #

已知A、B、C、D、W、X、Y、Z均为正整数，且满足：

1<=W<=A
1<=X<=B
1<=Y<=C
1<=Z<=D

求满足 W XOR X XOR Y XOR Z = 0 的无序四元组(W,X,Y,Z)的数量。这里的“无序”指排列不同但元素组合相同的四元组视为同一个（例如(2,2,3,3)与(2,3,2,3)是同一个四元组）。

原提问者最初误以为只有(n,n,n,n)或(n1,n1,n2,n2)这类四元组满足异或为0，后来发现(1,2,4,7)这类组合也符合条件，因此寻求解法。

解题步骤 #

1. 计算满足条件的有序四元组总数 #

异或等式 W XOR X XOR Y XOR Z = 0 等价于 W XOR X = Y XOR Z，可分两步统计：

• 统计所有X∈[1,B]、Y∈[1,C]的有序对中，异或结果为v的数量，记为字典cnt[v]。
• 统计所有W∈[1,A]、Z∈[1,D]的有序对中，异或结果为v的数量，记为字典cnt2[v]。
• 有序四元组总数 Total_order = 所有v对应的cnt[v] * cnt2[v]之和。

若A、B、C、D数值较小，直接遍历所有有序对统计即可；若数值较大（如1e9量级），则需用数位动态规划按二进制位逐位计算异或结果的频率，避免超时。

2. 将有序数量转换为无序数量 #

利用容斥原理，区分不同元素重复情况计算：

（1）四元素全相同的情况

即W=X=Y=Z=k，此时异或结果必然为0。统计满足1<=k<=min(A,B,C,D)的k的数量，记为S1。每个这样的四元组对应1个有序排列。

（2）两对相同元素的情况（如(a,a,b,b)，a≠b）

先统计所有满足W=X且Y=Z的有序四元组数量：S_order2 = min(A,B) * min(C,D)。该数值包含了a=b的情况（即四元素全相同），因此真正的两对不同元素的有序数量为S_order2 - S1。

每个无序的(a,a,b,b)对应6个有序排列（排列数为C(4,2)=6），因此这类无序四元组的数量 T2 = (S_order2 - S1) / 6。

（3）四个元素全不同的情况

这类情况的有序数量为 Total_order - S1 - 6*T2，每个无序四元组对应24个有序排列（4! =24），因此数量 T3 = (Total_order - S1 - 6*T2) / 24。

3. 最终结果 #

将三种情况的数量相加，得到总的无序四元组数量：
Total_unorder = S1 + T2 + T3

内容的提问来源于stack exchange，提问作者No Name