C. Master of Both IV

Solution

前置知识：线性基

线性基内的基元异或不会为 0 ，线性基插入失败等价于当前数与线性基的某些基元异或为 0

由此我们可以记录 插入失败的个数，记为$c$，则任选数异或为 0 的种类为 $2^c - 1$（排除空集)

题目要求：$\forall x\in[1,m],a_{i_x}|\bigoplus\limits_{j=1}^m a_{i_j}$

我们将异或结果分为两种：等于 0， 不等于 0

一、等于 0

0 是任何数的倍数， 把所有数插入线性基求插入失败次数 $c$ 贡献 $2^c - 1$

二、不等于 0

假设结果为 $f$，因为要整除，选的数必须为它的因子，

设因子为$f_1, f_2, f_3,…,f_n$ （不包括自己）

个数记为$c_1, c_2, c_3,…,c_n$ （不包括自己）

让因子的异或结果为 0， 再异或自己， 结果就是 $f$， 满足题目要求

把所有因子插入进线性基，同种数必定插入失败，直接加

插入失败的次数等于：$\sum\limits_{i = 1}^{n}(c_i - 1) + k$ (k为因子插入失败次数)

假设自己有 $c$ 个 要让结果不为 0 ，我们必须选奇数个， 有 $2^{c - 1}$ 种选法

贡献：$2^{c - 1} * 2^{(\sum\limits_{i = 1}^{n}(c_i - 1) + k)} = 2^{(\sum\limits_{i = 1}^{n}(c_i - 1) + k + c - 1)}$

二者相加即为结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;

template<int N>
struct linear_basis {
    long long siz;
    long long basis[N];
    linear_basis(){
        for(int i = 0;i < N;i++){
            basis[i] = 0;
        }
        siz = 0;
    }

    bool insert(long long x){
        for(int i = N - 1;~i;i--){
            if((x >> i) & 1){
                if(basis[i] == 0){
                    siz += 1;
                    basis[i] = x;
                    return true;
                }else{
                    x ^= basis[i];
                }
            }
        }
        return false;
    }
};

const int N = 20;
const int M = 2e5 + 10;
const int P = 998244353;

long long P2[M];
void prepare(){
    P2[0] = 1;
    for(int i = 1;i < M;i++){
        P2[i] = P2[i - 1] * 2 % P;
    }
}

long long power(long long a, long long b, long long p){
    long long ans = 1;
    a %= p;
    while(b){
        if(b & 1){
            ans = ans * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> cnt(n + 1);
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        cnt[a[i]] += 1;
    }

    vector<vector<pair<int, int>>> val(n + 1); 
    for(int i = 1;i <= n;i++){
        if(cnt[i]){
            for(int j = i * 2;j <= n;j += i){
                val[j].push_back({i, cnt[i]});
            }            
        }
    }

    long long ans = 0;
    for(int i = 1;i <= n;i++){
        if(cnt[i]){
            long long c = 0;
            linear_basis<N> line;
            for(auto& [x, y] : val[i]){
                c += y - 1;
                if(!line.insert(x)){
                    c += 1;
                }
            }
            long long tep = P2[cnt[i] - 1];
            long long tmp = P2[c] * tep % P;
            ans = (ans + tmp) % P;
        }
    }

    long long c = 0;
    linear_basis<N> line;
    for(int i = 1;i <= n;i++){
        if(!line.insert(a[i])){
            c += 1;
        }
    }
    ans = (ans + P2[c] - 1) % P;
    
    cout << ans << "\n";
};

int main(){
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    prepare();

    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}