描述
给定一个长度为 n 的非负整数序列 a[1..n]
你需要求有多少个非负整数 S 满足以下两个条件：
(1).0 ≤ S < 2^60
(2).对于所有 1 ≤ i < n ，有 (a[i] xor S) ≤ (a[i+1] xor S)
输入
第一行一个正整数 n
第二行 n 个非负整数表示序列 a[1..n]
1 ≤ n ≤ 50
0 ≤ a[i] < 2^60
输出
一个非负正数，表示答案
样例输入
3 1 2 3
样例输出
288230376151711744
分析：二进制，对每一位单独处理.比较大小先找不同的最高位，设分别为x1,x2.如果x1=1,x2=0,那么S的这一位必须是1,如果x1=0,x2=1，那么这一位必须是0，处理一下看有没有矛盾，没有矛盾的乘法原理解决.
#include <cstdio> #include <cmath> #include <queue> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; ll n, a[110], f[110][110], xianzhi[110], ans, maxn; bool flag = true; ll qpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res *= a; a *= a; b >>= 1; } return res; } int main() { memset(xianzhi, -1, sizeof(xianzhi)); for (int i = 1; i <= 60; i++) xianzhi[i] = -1; scanf("%lld", &n); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); for (int i = 2; i <= n; i++) { int pos = 0; ll temp, x1, x2; for (int j = 60; j >= 1; j--) { temp = (1 << (j - 1)), x1 = 0, x2 = 0; if (temp & a[i - 1]) x1 = 1; if (temp & a[i]) x2 = 1; if (x1 != x2) { pos = j; break; } } if (pos == 0) continue; if (x1 > x2) { if (xianzhi[pos] == -1) xianzhi[pos] = 1; if (xianzhi[pos] == 0) { flag = false; break; } } else { if (xianzhi[pos] == -1) xianzhi[pos] = 0; if (xianzhi[pos] == 1) { flag = false; break; } } } if (!flag) puts("0"); else { ans = 1; for (int i = 1; i <= 60; i++) if (xianzhi[i] == -1) ans <<= 1; printf("%lld ", ans); } return 0; }