题目1 : 异或排序

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一个长度为 n 的非负整数序列 a[1..n]

你需要求有多少个非负整数 S 满足以下两个条件：

(1).0 ≤ S < 260

(2).对于所有 1 ≤ i < n ，有 (a[i] xor S) ≤ (a[i+1] xor S)

输入

第一行一个正整数 n

第二行 n 个非负整数表示序列 a[1..n]

1 ≤ n ≤ 50

0 ≤ a[i] < 260

输出

一个非负正数，表示答案

样例输入

31 2 3

样例输出

288230376151711744

 

/*    Name: xor sort    Copyright:@2017 shenben     Author: shenben    Date: 25/04/17 15:32    Description: // a[i] xor a[i+1] = (a[i] xor S) xor (a[i+1] xor S)// 假如a[i] xor a[i+1]的是1的最高位是第k[i]位// 只需判断a[i] xor S的第k[i]位，是0则S满足，是1则S不满足// 所以符合要求的S必须满足对于所有1 <= i < n，有S的第k[i]位与a[i]的第k[i]位相同*/#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;template 
         
          inline void read(T &x){    T f=1;char ch=getchar();x=0;    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    x*=f;}const int N=65;int n;ll a[N];short k[N];inline void make(int x,int y){    if(k[x]==-1) k[x]=y;else    if(k[x]!=y){puts("0");exit(0);}}int main(){    read(n);memset(k,-1,sizeof k);    for(int i=1;i<=n;i++) read(a[i]);    for(int i=1;i
          
           >j)&1); break; } } } ll ans=1; for(int i=0;i<60;i++) if(k[i]==-1) ans<<=1; cout<
           
            <<'\n'; return 0;}