5043: [Lydsy1709月赛]密码破译


Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 477  Solved: 125
[Submit][Status][Discuss]

Description


小Q发明了一个新的加密算法,对于一个长度为n的非负整数序列a_1,a_2,...,a_n,他会随机选择一个非负整数k,

将每个数都异或上k得到b_1,b_2,...,b_n,即b_i=a_i xor k。不幸的是,健忘的小Q睡了一觉之后就把密钥k忘得
一干二净了,不过他隐约记得a_1+a_2+...+a_n的值为m,你能帮他找到一个可行的密钥吗
 

Input


第一行包含两个整数n,m(1<=n<=100000,0<=m<2^{60}),分别表示序列的长度以及加密前所有数的和。
第二行包含n个整数b_1,b_2,...,b_n(0<=b_i<2^{60}),表示加密后的序列。
 

Output


输出一个非负整数k,若无解输出-1,若有多组解,输出最小的k。

 

Sample Input


  

Sample Output


HINT


 

Source


本OJ付费获取

分析:


这种与位运算有关的,大多数都是拆开按位从高到低贪心,或者从低到高dp。

这道题就是定义f[i][j]表示i位能向下一位进j个(1<<i);

记录每一位数字总和,讨论每一位k是0或1再与m的每一位是0或1作比,从低到高dp一遍就好了

j最多是n所以复杂度是O(60*n)

AC代码:


# include <iostream>
# include <cstdio>
using namespace std;
const int N = 1e5 + ;
typedef long long LL;
const LL inf = 1LL << ;
LL f[][N],p[],m,x;int n;
int main()
{
scanf("%d %lld",&n,&m);
for(int i = ;i <= n;i++)
{
scanf("%lld",&x);
for(int j = ;~j;j--)
p[j + ] += x >> j & ;
}
for(int i = ;i <= n;i++)
for(int j = ;~j;j--)
f[j][i] = inf;
f[][] = ;
for(int j = ;j <= ;j++)
{
for(int i = ;i <= n;i++)
{
if(((p[j + ] + i) & ) == (m >> j & ))
f[j + ][(p[j + ] + i) >> ] = min(f[j + ][(p[j + ] + i) >> ],f[j][i]);
if(((n - p[j + ] + i) & ) == (m >> j & ))
f[j + ][(n - p[j + ] + i) >> ] = min(f[j + ][(n - p[j + ] + i) >> ],f[j][i] + (1LL << j));
}
}
printf("%lld\n",f[][] == inf ? - : f[][]);
}
05-11 17:35