题解：P13685 【MX-X16-T3】「DLESS-3」XOR and Impossible Problem

luogu_gza · 2025-08-10 19:42:00 · 题解

我们令集合 A=\{a_i|1 \leq i \leq n \land a_i \bmod 2=1\}，B=\{a_i|1 \leq i \leq n \land a_i \bmod 2=0\}。

显然 A 中任意两个数异或值一定是 2 的倍数，B 中任意两个数异或值也一定是 2 的倍数，因此答案至少是 2^{\frac{|A|(|A|-1)}{2}+\frac{|B|(|B|-1)}{2}} \geq 2^{\lfloor \frac n2 \rfloor(\lfloor \frac n2 \rfloor- 1)} 的倍数，因此在 n \geq 70（这个界很松我乱取的）的时候直接输出 0，其他时候跑暴力就行了。

核心代码：

const int N=1e6+10;
int n;
int a[N];
void solve()
{
  n=R;
  fo(i,1,n) a[i]=R;
  if(n>=70) puts("0");
  else
  {
    unsigned int ans=1;
    fo(i,1,n) fo(j,i+1,n) ans*=(a[i]^a[j]);
    write(ans),puts("");
  }
}
void main(){
  MT solve();
}