Розв'язок

Загальна ідея: Ми хочемо мінімізувати кількість інверсій бітів таким чином, щоб існував підмасив, OR якого дорівнює k.

Зазначимо, що інверсія бітової позиції p еквівалентна примусу цього біта відповідати відповідному біту в k. Таким чином, для будь-якого підмасиву зі значенням OR x, кількість необхідних операцій є просто кількістю відмінних біт:

Отже, задача зводиться до ефективного перерахунку всіх можливих значень OR підмасивів.

Ключове зауваження: Під час ітерації через масив зліва направо, кількість різних значень OR підмасивів, що закінчуються на позиції i, є незначною — не більше приблизно 30.

Чому? Тому що кожен раз, коли ми застосовуємо OR, біти можуть змінюватись лише з 0 на 1. Оскільки цілі числа мають не більше 30 біт, кожен біт можна встановити лише один раз.

Алгоритм: Підтримуйте вектор, що зберігає пари (значення, старт), які представляють різні значення OR для підмасивів, що закінчуються на поточному індексі.

Для кожного елементу:

• Почніть новий підмасив з OR, рівним a[i].

• Виконайте OR з усіма раніше збереженими значеннями.

• Об'єднайте дублікати, щоб тримати вектор маленьким.

• Для кожного значення OR x обчисліть \text{popcount}(x \oplus k) і оновіть відповідь.

Нарешті, виведіть позиції бітів, які відрізняються між найкращим значенням OR і k.

Аналіз складності:

Хоча може здаватися, що ми перевіряємо багато підмасивів, кількість різних значень OR на індекс обмежена кількістю біт (не більше 30).

Для кожного з n елементів ми обробляємо не більше 30 різних значень OR.

Отже, часова складність є:

Складність за пам'яттю: \mathcal{O}(30) = \mathcal{O}(1) для зберігання різних значень OR на кожній позиції.

Референсна реалізація

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<pair<int, int>> v; 
    int ans = 30, pos = 0;
    
    for (int i = 1; i <= n; i++) {
        vector<pair<int, int>> u;
        u.push_back({a[i], 1});
        
        for (auto [x, c] : v) {
            int g = (x | a[i]);
            if (g == u.back().first) {
                u.back().second = c;
            } else {
                u.push_back({g, c});
            }
        }
        
        v = u;
        
        for (auto [x, c] : v) {
            int cnt = (x ^ k);
            int res = __builtin_popcount(cnt);
            if (res <= ans) {
                ans = res;
                pos = cnt;
            }
        }
    }
    
    cout << ans << "\n";
    for (int i = 0; i < 30; i++) {
        if (pos & (1 << i)) {
            cout << i << " ";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << "\n";
    }
    return 0;
}