题解：P13685 【MX-X16-T3】「DLESS-3」XOR and Impossible Problem
Link
题目思路
求：
\[\prod_{i=1}^n\prod_{j=i+1}^n(a_i\oplus a_j) \bmod 2^{64}
\]
令 \(A=\{a_i| \bmod 2=1\}\)，\(B=\{a_i|1 \bmod 2=0\}\)，用 \(f(a)\) 表示 \(\prod_{i=1}^n\prod_{j=i+1}^n(a_i\oplus a_j)\) 中因子 \(2\) 的最小数量。数的总数为 \(|a|\)。
根据异或的性质，\(A\) 和 \(B\) 中任意两个数异或一定含有因子 \(2\)。考虑确定一个界，在此情况下 \(|A|+|B|\) 为最小值且此时 \(f(a) \ge 64\)。当 \(f(a) > 64\) 时，\(\prod_{i=1}^n\prod_{j=i+1}^n(a_i\oplus a_j) \bmod 2^{64} \equiv 0 \pmod{2^{64}}\)。直接输出 \(0\) 即可。我们可得：
\[\min_a f(a)= \binom{|A|}{2} +\binom{|B|}{2}=\frac{|A|(|A|-1)}{2}+\frac{|B|(|B|-1)}{2}
\]
当 \(|A|=8,|B|=9\) 时：
\[\min_a f(a)= \binom{|A|}{2} +\binom{|B|}{2}=\binom{8}{2} + \binom{9}{2}= 64
\]
综上，\(|a| <17\) 时，\(f(a)<64\)。$|a| \ge 17 $ 时，\(f(a) \ge 64\)。
故答案为：
\[\prod_{i=1}^n\prod_{j=i+1}^n(a_i\oplus a_j) \bmod 2^{64} =
\begin{cases}
0 & \text{if } |a| \ge 17 \\
\prod_{i=1}^n\prod_{j=i+1}^n(a_i\oplus a_j) \bmod 2^{64} & \text{if } |a| < 17
\end{cases}
\]
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
const int N=1e6+10;
ll T,n;
LL a[N],b;
int main() {cin>>T;while(T--){cin>>n;if(n>=17){for(int i=0;i<n;i++) cin>>b;cout<<"0\n";} else{for(int i=0;i<n;i++) cin>>a[i];LL ans=1;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){ans=ans*(a[i]^a[j]);}}cout<<ans<<"\n";}}return 0;
}