hihoCoder Challenge 28 异或问题 思维

Given a sequence a[1..n], you need to calculate how many integers S satisfy the following conditions:

(1). 0 ≤ S < 260

(2). For every i in [1,n-1] , (a[i] xor S) ≤ (a[i+1] xor S)

Input
On the first line there is only one integer n

On the second line there are n integers a[1..n]

1 ≤ n ≤ 50

0 ≤ a[i] < 260

Output
Output one integer : the answer

Sample Input
3
1 2 3
Sample Output
288230376151711744

题目大意很明确，思路是什么？
看到异或自然想到二进制，
比如：
00011101
00011010
比较大小从高到低进行比较，如果在某一位置开始出现不同，那么自然异或值S这一位就确定了，因为相同的异或结果还是相同，所以只需要确定哪些位置已经被确定了，那么总方案数就是 2^( 未确定位置数量 ).

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 2000005
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;

ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9') {
        if (ch == '-') {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0'&&ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

ll quickpow(ll a, ll b) {
    ll ans = 1;
    while (b > 0) {
        if (b % 2)ans = ans * a;
        b = b / 2;
        a = a * a;
    }
    return ans;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}


bool cmp(int a, int b) {
    return a > b;
}

ll ves[maxn];
void revs() {
    for (ll i = 1; i <= 1000000; i++) {
        ves[i] = quickpow(i, mod - 2);
    }
}


//ull Mod = quickpow(2ull, 47ull);
ll a[100];
int b1[100], b2[100];
int v[100];
ll ans;
void dl(ll x, ll y) {
    int i, j;
    for (int i = 1; i <= 60; i++) {
        b1[i] = x % 2;
        x = x / 2;
    }
    for (int j = 1; j <= 60; j++) {
        b2[j] = y % 2;
        y = y / 2;
    }
     ans = 0;
    for (int i = 60; i >= 1; i--) {
        if (b1[i] == b2[i])continue;
        ans = i;
        break;
    }
    v[ans] = 1;
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)cin >> a[i];
    for (int i = 0; i < n - 1; i++)dl(a[i], a[i + 1]);
    ans = 0;
    for (int i = 60; i >= 1; i--) {
        if (v[i])continue;
        ans++;
    }
    ans = (ll)1 << ans;
    cout << ans << endl;
}