我需要一些帮助，我归纳为以下的一个问题。我有N个30比特数，使得所有这些的组合异或为非零。我需要一个非负（0或更多）值添加到每个N个数字，这样，新的数字的组合的异或变为0时，限制下的总加法值（不相加次数）最小化

I need some help with a problem that I have reduced to the following. I have N 30 bit numbers, such that the combined XOR of all of them is non-zero. I need to add a non-negative (0 or more) value to each of the N numbers, such that the combined XOR of the new numbers becomes 0, under the constraint that the total addition value (not the number of additions) is minimized.

例如，如果我有数字（01010） 2 ，（01011） 2 和（01100） 2 为三个数字（N = 3）。然后，他们的组合是异或（01101） 2 。我们可以按如下方式添加一些数字：

For example, if I had numbers (01010)2, (01011)2 and (01100)2 as three numbers (N = 3). Then, their combined XOR is (01101)2. We could add some numbers as follows:

（01010） 2 +（00001） 2 =（01011） 2 ：（+1） （01011） 2 +（10000） 2 =（11011） 2 ：（+16） （01100） 2 +（00100） 2 =（10000） 2 ：（+4） (01010)2 + (00001)2 = (01011)2 : (+1) (01011)2 + (10000)2 = (11011)2 : (+16) (01100)2 + (00100)2 = (10000)2 : (+4)

现在，新的号码的总异或为0，且总加入量为21（= + 1 + 16 + 4）。这个总数除值必须最小（有可能是一个更好的分布，减少其中，但是这仅仅是一个的例如的）。

Now, the total XOR of the new numbers is 0, and the total addition is 21 (=+1+16+4). This total addition value has to be minimized (there could be a better distribution which reduces this total, but this is just an example).

这些数字是各30位，这样的数字可能会很大，和N = 15，我真的AP preciate，如果有人能证明，以解决这方面的一些有效的方法。我怀疑一个DP的解决方案是可能的，但我不能制定任何东西。

These numbers are 30 bits each, so the numbers could be large, and N <= 15. I would really appreciate it if someone could show some efficient way to solve this. I suspect a DP solution is possible, but I could not formulate anything.

谢谢！

推荐答案

尼斯问题：）

我想出了这为O（N * 2 ^ N * 31 * N）的方法，对于n = 15，它是一个有点慢（228556800）的一个测试案例。下面是详细信息：

I have come up with an approach which runs in O(n * 2^n * 31 * n), for n = 15, it 's a bit slow (228556800) for one test case. Here are the details:

我使用的是DP的方法（记忆化）在这里，我们定义了一个状态（INT面膜，INT POS）：

I use a dp approach(memoization) here, we define a state as (int mask, int pos):

面膜

mask

0℃=掩模＆其中; 2 ^ N - 1，如果2 ^ I和掩模> 0时，我们指数i已被添加之前，所有的较低位（小于=正）。可以认为是零

0 <= mask < 2^n - 1, if 2^i & mask > 0, we mean number i has been added before, and all lower bit(<=pos) can be considered as zero.

POS

当前的校验位的位置，从高开始向低

current check bit position, start from high to low

我们从最高位开始到最低位，而每次我们检查给定的数字具有当前位组的计数时间，我们记为one_cnt，如果

We start from highest bit to lowest bit, and each time we check the count of the given numbers which have current bit set, we denote it as one_cnt, if

one_cnt甚至

one_cnt is even

当前位置的XOR是零，我们只是移动（面具，POS - 1）

current pos's xor is zero, we just move to (mask, pos - 1)

one_cnt是奇数

one_cnt is odd

如果one_cnt等于N（全单数），在这里我们考虑作为一个糟糕的状态，什么也不做。否则，我们就迭代包含零POS机，并尝试在这里放置一个数字。

if one_cnt equals to n (full odd), here we consider as an bad state and do nothing. Otherwise we iterate on numbers which contain zero at pos and try to place a one here.

注意这里的时候one_cnt满奇怪的，我们认为它是坏的状态，因为我们不想增加至（POS + 1）whcich可能会影响previous状态（违反DP原则）。

Notice here when one_cnt is full odd, we consider it as bad state because we don't want to increase to (pos + 1) whcich may affect previous state (violate the dp principle).

但是会出现这样的情况：改编= [1，1，1]和溶液存在。所以在这里，我们尝试做一些额外的计算：

But there will be such case: arr = [1, 1, 1] and the solution exists. So here we try to do some extra computing:

我们从最高位的POS启动和检查，如果当前比特包含的甚至一位，如果是这样，我们遍历上的数字来设置1到一个数字零在当前位置，然后我们开始记忆化和更新我们的结果。

We start from the highest bit pos and check if current bit contain even one bit, if so we iterate on the numbers to set 1 to one number with zero in current pos, then we start our memoization and update our result.

例如，如果ARR = 1，1，1]中，我们可以检查[2，1,1]，[1,2,1]，[1,1,2]

For example if arr = [1, 1, 1], we may check [2, 1, 1], [1,2,1], [1,1,2]

希望我已经解释得很好。

Hope I've explained it well.

我会更新的解决方案，如果我想出更快的办法：）

I will update the solution if I come up with faster approach :)

下面是code：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <ctime>
#include <cassert>

using namespace std;

#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define range(i, n) for (long long i=0; i<(n); ++i)
#define forit(it,v) for(typeof((v).begin()) it = v.begin() ; it != (v).end() ; ++it)
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),a.end()
#define two(i) (1LL<<(i))

typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;

int n;
vector<ll>  arr;
ll ans;
map<PII, ll> M;

void update(ll & ret, ll tmp) {
    if (tmp == -1) return;
    if (ret == -1) ret = tmp;
    ret = min(ret, tmp);
}

/*
 * memoization(mask, pos)
 * Args:
 * mask: if 2^i in mask it means arr[i] has been added a high bit before, and all lower bit(<=pos) can be considerd zero.
 * pos: current check bit position, start from high to low
 * Return:
 *  return -1 if not valid ans exists else return minimum addition sum 
 */
int memoization(int mask, int pos) {

    if (pos < 0) {
        return 0;
    }

    PII state = mp(mask, pos);
    if (M.find(state) != M.end()) {
        return M[state];
    }

    ll &ret = M[state];
    ret = -1;

    int one_cnt = 0;
    for (int i = 0; i < n; i++) {
        if ( !(mask & two(i)) && 
                (two(pos) & arr[i])) {
            one_cnt ++;
        }
    }

    if (one_cnt % 2 == 0) { // even, xor on this pos equals zero
        ret = memoization(mask, pos - 1);
    } else {
        if (one_cnt == n)  { //full odd  bad state, do nothing
            //pass
        } else { //not full odd, choose one empty bit  to place 1  
            for (int i = 0; i < n; i++) {
                if ((mask & two(i))  //if number i has been added before, then it contain zero at pos 
                        || !(two(pos) & arr[i])  // or if number i has zero at pos and hasn't been added before
                        ) {
                    ll candi = memoization(mask | two(i), pos - 1);
                    ll added = mask & two(i) ? two(pos)  // number i has been added before, so we need extra two(pos) sum
                        //number i hasn't been added before, we need calc the new sum 
                        //here we only consider bits in [0 .. pos]
                        : two(pos) - arr[i] % two(pos + 1); 
                    if (candi >= 0)  // legal result
                        update(ret,  candi + added);
                }
            }
        }
    }

    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("g.in", "r", stdin);
#endif
    while (cin >> n) {
        arr.clear();
        for (int i = 0; i < n; i++) {
            ll val;
            cin >> val;
            arr.push_back(val);
        }

        ll max_val = arr[0];
        for (int i = 1; i < n; i++) max_val = max(max_val, arr[i]);

        int max_pos = 0;
        while (max_val) max_pos ++, max_val >>= 1;
        max_pos ++;

        //no adjust
        M.clear();
        ans = memoization(0, 31);

        bool even_bit = true;
        for (int i = max_pos; i >= 0; i--) {
            int one_cnt = 0;

            for (int j = 0; j < n; j++) one_cnt += (two(i) & arr[j]) > 0;
            even_bit &= one_cnt % 2 == 0;

            if (even_bit) {
                for (int j = 0; j < n; j++) {
                    //arr[j] at pos i is empty, try add to 1
                    if (!(two(i) & arr[j])) {
                        ll backup = arr[j];
                        arr[j] = two(i);

                        //since previous pos all contain even one bits, we just start from current pos i
                        M.clear();
                        ll candi = memoization(0, i);
                        ll added = two(i) - backup % two(i);
                        if (candi >= 0) 
                            update(ans, candi + added);

                        arr[j] = backup;
                    }
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}