题目链接：https://codeforces.com/gym/102156/problem/D

题目大意：

给你 $n$ 个数字，再给你 $m$ 组数字，你要在每一组里面选一个数字，使得选出来的数字和那 $n$ 个数字，关于异或运算线性无关，如果可以，给一组方案。

做法

有限大小的线性空间本身就是拟阵，这样就很显然了。

  1. 拟阵 $1$ 是线性无关。（算上那 $n$ 个数字）
  2. 拟阵 $2$ 是每组数字至多一个。

时间复杂度：$O(60^2\sum\limits k_i)$ 。

记得特判一开始的 $n$ 个数字是否线性无关，否则还是老生常谈的问题：$\emptyset\notin \mathcal{I}$ 。

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N1=65;
const int N2=5e3+5;
const int M=6e5+5;
int n,m,K;
LL va[N2];int bel[N2];
bool col[N1],in[N2];

LL sta[N1];
int pos[N1],top;
LL lin[N1],fac[N1];
bool add(LL x,int id){
    LL now=(1ll<<(id-1));
    for(int i=59;i>=0;i--){
        if((x>>i)&1){
            if(!lin[i]){
                lin[i]=x;
                fac[i]=now;
                return 1;
            }
            else x^=lin[i],now^=fac[i];
        }
    }
    return 0;
}
bool build_liner(){
    memset(lin,0,sizeof(lin));
    memset(fac,0,sizeof(fac));
    for(int i=1;i<=top;i++){
        if(!add(sta[i],i))return 0;
    }
    return 1;
}
LL findfac(LL x){
    LL now=0;
    for(int i=59;i>=0;i--){
        if((x>>i)&1){
            if(!lin[i])return -1;
            else x^=lin[i],now^=fac[i];
        }
    }
    return now;
}

struct node{
    int y,next;
}a[M];int len,las[N2];
void ins(int x,int y){a[++len]={y,las[x]};las[x]=len;}
int typ[N2];
void getliner(){
    top=n;
    for(int i=1;i<=K;i++){
        if(in[i])sta[++top]=va[i],pos[top]=i;
    }
    assert(build_liner());
}
void build(){
    len=0;
    memset(las+1,0,sizeof(int)*K);
    memset(typ+1,0,sizeof(int)*K);
    getliner();
    for(int now=n+1,i=pos[now];now<=top;now++,i=pos[now]){
        for(int j=1;j<=K;j++){
            if(in[j])continue;
            if(bel[i]==bel[j] || !col[bel[j]])ins(j,i);
        }
    }
    for(int i=1;i<=K;i++){
        if(in[i])continue;
        LL x=findfac(va[i]);
        if(x==-1){
            typ[i]|=1;
            x=(1ll<<top)-1;
        }
        for(int now=n+1;now<=top;now++){
            if((x>>(now-1))&1)ins(pos[now],i);
        }
        if(!col[bel[i]])typ[i]|=2;
    }
}
queue<int> q;
int pre[N2];
bool solve(){
    for(int i=1;i<=K;i++)pre[i]=-1;
    for(int i=1;i<=K;i++){
        if(typ[i]&1){
            pre[i]=0;
            q.push(i);
        }
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        if(typ[x]&2){
            while(!q.empty())q.pop();
            while(x){
                col[bel[x]]^=1;
                in[x]^=1;
                x=pre[x];
            }
            return 1;
        }
        for(int k=las[x];k;k=a[k].next){
            int y=a[k].y;
            if(pre[y]==-1){
                pre[y]=x;
                q.push(y);
            }
        }
    }
    return 0;
}

int main(){
    scanf("%d",&n);top=n;
    for(int i=1;i<=n;i++)scanf("%lld",&sta[i]);
    if(!build_liner()){
        printf("-1\n");
        return 0;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int cnt;scanf("%d",&cnt);
        for(int j=1;j<=cnt;j++){
            ++K;bel[K]=i;
            scanf("%lld",&va[K]);
        }
    }
    for(int i=1;i<=m;i++){
        build();
        if(!solve()){
            printf("-1\n");
            return 0;
        }
    }
    for(int i=1;i<=K;i++){
        if(in[i])printf("%lld\n",va[i]);
    }
    return 0;
}