题目链接：http://hihocoder.com/problemset/problem/1509
解题方案：首先，两个数谁大谁小一定是看这两个数的高位里面第一个不相同的数字，不管是10进制还是2进制都是这样判断。然后可以将所有的a[i]看成是60位的二进制数，a[i]和a[i+1]二进制串相同的地方和s异或后一定还是一样的，不同的地方和s异或后一定还是不一样的，因为（0,1）^0=（0,1），（0,1）^1=（1,0），（0,0）^0=（0,0），（1,1）^1=（0,0）。所以s的二进制串若想满足题意，对a[i]和a[i+1]高位里面第一个不相同的位置j，s[j]是固定的。故只需要将s所有固定的位置的值求出来，期间判断一下是否出现矛盾，然后就可以算出符合题意的s的个数了。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <vector> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define FOR(i,k,n) for(int i=k;i<n;i++) #define FORR(i,k,n) for(int i=k;i<=n;i++) #define scan(a) scanf("%d",&a) #define scann(a,b) scanf("%d%d",&a,&b) #define scannn(a,b,c) scanf("%d%d%d",&a,&b,&c) #define mst(a,n) memset(a,n,sizeof(a)) #define ll long long #define N 65 #define mod 1000000007 #define INF 0x3f3f3f3f const double eps=1e-8; const double pi=acos(-1.0); int a[N][N]; int s[N]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; while(cin>>n) { mst(a,0); mst(s,-1); FOR(i,0,n) { ll tmp; cin>>tmp; int cnt=0; while(tmp) { a[i][cnt++]=tmp&1; tmp>>=1; } } int flag=1; FOR(i,0,n-1) { if(!flag) break; for(int j=59;j>=0;j--) { if(a[i][j]!=a[i+1][j]) { if(a[i][j]==0&&a[i+1][j]==1) { if(s[j]==1) { flag=0; break; } s[j]=0; } else { if(s[j]==0) { flag=0; break; } s[j]=1; } break; } } } if(!flag) printf("0\n"); else { int cnt=0; FOR(i,0,60) if(s[i]==-1) cnt++; //printf("%d\n",cnt); cout<< ((ll)(1)<<cnt) <<endl; } } return 0; }
