Nhận xét: để ý rằng từ ~1~ đến ~5000~ thì số nguyên tố lớn nhất có thể tạo ra mà bằng tổng XOR của các số khác chỉ có thể là ~8191~. Tránh bị TLE thì ta sẽ sàng nguyên tố để tìm các số nguyên tố từ ~1~ đến ~8192~, như vậy là ta có thể đoán độ phức tạp là: ~O(T \times 1000 \times 8191)~

Xử lý các kết quả bị trùng lặp thì ta sẽ:

Gọi ~v~ là mảng lưu các phần tử khác nhau trong ~a~

Gọi ~c~ là mảng để đếm số lần xuất hiện của các phần tử trong ~a~

Gọi ~f[i][j]~ là số lượng tập con có thể tạo ra với ~i~ phần tử sao cho tổng XOR của ~i~ phần tử này bằng ~j~

Cơ sở: ~f[0][0] = 1~

Nhận xét: để ý thêm rằng ~f[0][j]~ sẽ phải bằng tổng của các ~f[1][j]~ và ngược lại ( áp dụng rolling array ), vì thế ta sẽ có biến ~ind~ và ban đầu khởi tạo ~ind = 1~ và mỗi lần duyệt thì ta sẽ flip biến ~ind~ là: ~ind = ind \oplus 1~.

Như vậy tại mỗi lần duyệt ta sẽ có ~f[ind][j]~ sẽ bằng tổng của số lượng tập con tại:

• ~f[ind \oplus 1][j] \times (1 + \frac{c[v[i]]}{2})~ là số lượng tập con trước đó có tổng XOR là ~j~ nhân với ~1~ nửa số lượng số lần xuất hiện của ~v[i]~

• ~f[ind \oplus 1][j \oplus v[i]] \times (\frac{1+c[v[i]]}{2})~ là số lượng tập con trước đó có tổng XOR là ~j \oplus v[i]~ nhân với ~1~ nửa số lần xuất hiện còn lại của ~v[i]~

Như vậy, công thức đầy đủ của ta sẽ là: ~f[ind \oplus 1][j] \times (1+\frac{c[v[i]]}{2}) + f[ind \oplus 1][j \oplus v[i]] \times (\frac{1+c[v[i]]}{2})~

Lưu ý: các phép toán cần thực hiện lấy dư cho ~10^9+7~ để tránh bị tràn.

Code mẫu

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

const int MOD = 1e9 + 7;

void Add(int &x, int y) {
    x += y;
    if (x >= MOD)
        x -= MOD;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> cnt(5001, 0);
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            cnt[x]++;
        }
        vector<int> dp(1 << 13, 0);
        dp[0] = 1;
        for (int x = 1; x <= 5000; x++) {
            if (!cnt[x])
                continue;
            vector<int> nxt(1 << 13, 0);
            for (int i = 0; i < (1 << 13); i++) {
                Add(nxt[i], 1ll * dp[i] * (cnt[x] / 2 + 1) % MOD);
                Add(nxt[i ^ x], 1ll * dp[i] * ((cnt[x] + 1) / 2) % MOD);
            }
            dp = nxt;
        }
        int res = 0;
        for (int i = 2; i < (1 << 13); i++) {
            if (dp[i] == -1)
                continue;
            Add(res, dp[i]);
            for (int j = 2 * i; j < (1 << 13); j += i)
                dp[j] = -1;
        }
        cout << res << '\n';
    }
    return 0;
}