题意
给你(n)个在([0, 2^{60}))的数字(a_1, ..., a_n)，首先用这些数字构造一个线性基，设这个线性基是群(G)
然后构造一个映射(f: G o G)，满足题目中写的三个条件
这个题有两个subtask
subtask1是，让你构造出这样的一个映射(f)，如果不存在输出无解，否则，他会告诉你一些(x)，你要告诉他对应的(f(x))，通过这样的方法检验正确性
subtaks2是，给你一个映射(f)，还有一些(x)和对应的(f(x))，问你这组解是否合法
（这题的spj也就是subtask2是比subtask1难的，感受到了出题人的恶意233333）
题解
需要一些抽代基础，怪不得高中爷爷们不会这个题2333333
首先存在一个集合(S)，(S)中所有元素的image是(0)，这个(S)称为(G)的Kernal，记为(K)
首先，(K)一定是(G)的subgroup
然后，Lagrange定理告诉我们，(K)的阶整除(G)的阶
显然，(K)一定是从线性基中选若干个线性无关组，由这些向量张成空间(K)
题目中第三条告诉我们(f)是一个homomorphism，设(f)的像集是(G')，同构定理告诉我们(G/K cong G')
观察题目中前两条限制，这是在告诉我们，像集(G' = K)，证明就是下面这个式子
那么我们就惊人的发现(G/K cong K)，由Lagrange定理得到(|K| = sqrt{|G|})
因此，(G)的rank必须是偶数，否则无解
然后我们考虑subtask1
设(G)的rank是(r)，从(r)个线性无关向量中任取(r/2)个，都可以张成这样一个Kernal，并且可以构造出符合条件的(f)，构造如下
首先丢掉所有不重要的二进制位，只保留(r)位重要的（这个自己意会吧。。）
这个时候，(r)个基向量就是(r imes r)的单位矩阵(E)的这(r)行
不妨假设我们取了前(r/2)个向量(v_1, ..., v_{r/2})张成Kernal(K)
那么(K)中的元素，后(r/2)位都是(0)
紧接着，观察发现，考虑(K)的所有coset，发现如果两个数字在同一个coset中，那么这两个数字的后(r/2)位一定相同
假设后(r/2)位的第(b_1, b_2, ..., b_p)位是(1)，其他位是(0)，那么这个陪集的元素都映射到“张成Kernal的基的第(b_1, b_2, ..., b_p)个向量的异或和”
构造完了，也很好写，需要注意的是，求线性基的时候需要特殊处理一下，如果某一列出现了主元，那么这一列其他的位置都要消成(0)
然后考虑subtask2，首先把-1判掉
首先，出现在(f(x))中的值，都在Kernal中，因此拿这些值做一个线性基（带着左边的(x)一起消元）
消元了之后，假如原来有个pair((x, f(x)))现在变成了((x', 0))，那么显然(x')也应该加入到Kernal中
这两步做完之后，我们已经得到了我们能知道的Kernal最大的子空间，检查这个子空间的rank，如果大于(r/2)就无解
现在还有一些pair在消元之后(f(x))仍然不是(0)，我们需要检查这些pair的(x')是否线性无关，如果她们线性相关，那么对(x')消元就可以得到(f(0) eq 0)，因此如果线性相关则无解
最后，检查这些(x')是否不在Kernal这个线性基中，如果都不在，那么这就是一组合法的解
证明思路：其实这些(x')就是不同陪集的代表元，这些(x')张成的空间与(G/K)的一个子空间是同构的
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010;
int _w;
int n;
ll a[N];
struct Basis {
ll b[60];
void clear() {
memset(b, 0, sizeof b);
}
bool insert( ll x ) {
for( int i = 0; i < 60; ++i )
if( x & (1LL << i) ) {
if( b[i] ) {
x ^= b[i];
} else {
b[i] = x;
for( int j = i+1; j < 60; ++j )
if( b[j] )
if( b[i] & (1LL << j) )
b[i] ^= b[j];
for( int j = 0; j < i; ++j )
if( b[j] & (1LL << i) )
b[j] ^= b[i];
return true;
}
}
return false;
}
int size() {
int ans = 0;
for( int i = 0; i < 60; ++i )
ans += bool(b[i]);
return ans;
}
bool inside( ll x ) {
for( int i = 0; i < 60; ++i )
if( x & (1LL << i) ) {
if( b[i] ) {
x ^= b[i];
} else {
return false;
}
}
return true;
}
};
void construct() {
Basis bas;
bas.clear();
for( int i = 1; i <= n; ++i )
bas.insert( a[i] );
if( bas.size() % 2 == 1 ) {
puts("NoSolution");
int m;
_w = scanf( "%d", &m );
while( m-- ) {
ll x;
_w = scanf( "%lld", &x );
}
} else {
puts("HaveSolution");
vector<int> bit;
for( int i = 0; i < 60; ++i )
if( bas.b[i] )
bit.push_back(i);
int sz = (int)bit.size();
int q;
_w = scanf( "%d", &q );
while( q-- ) {
ll x;
_w = scanf( "%lld", &x );
if( bas.inside(x) ) {
ll y = 0;
for( int i = sz/2; i < sz; ++i ) {
int b = bit[i];
if( x & (1LL << b) )
y ^= bas.b[bit[i-sz/2]];
}
printf( "%lld
", y );
} else {
puts("-1");
}
}
}
}
namespace Check {
typedef pair<ll,ll> pii;
int m;
pii xy[N];
vector<ll> zero;
pii by[60];
void insert_by( pii now ) {
ll x = now.first;
ll y = now.second;
for( int i = 0; i < 60; ++i )
if( y & (1LL << i) ) {
if( by[i].second == 0 ) {
by[i] = pii(x, y);
for( int j = i+1; j < 60; ++j )
if( by[j].second )
if( by[i].second & (1LL << j) ) {
by[i].second ^= by[j].second;
by[i].first ^= by[j].first;
}
for( int j = 0; j < i; ++j )
if( by[j].second & (1LL << i) ) {
by[j].second ^= by[i].second;
by[j].first ^= by[i].first;
}
return;
} else {
y ^= by[i].second;
x ^= by[i].first;
}
}
zero.push_back(x);
}
void check() {
Basis bas;
bas.clear();
for( int i = 1; i <= n; ++i )
bas.insert( a[i] );
string state;
cin >> state;
if( (state == "NoSolution" && bas.size() % 2 == 0) ||
(state == "HaveSolution" && bas.size() % 2 == 1) ) {
puts("No");
if( state == "HaveSolution" ) {
int m;
_w = scanf( "%d", &m );
while( m-- ) {
ll x, fx;
_w = scanf( "%lld%lld", &x, &fx );
}
}
} else {
if( state == "NoSolution" ) {
puts("Yes");
return;
}
_w = scanf( "%d", &m );
for( int i = 1; i <= m; ++i ) {
ll x, y;
_w = scanf( "%lld%lld", &x, &y );
xy[i] = pii(x, y);
}
for( int i = 1; i <= m; ++i ) {
if( (bas.inside( xy[i].first ) && xy[i].second == -1) ||
(bas.inside( xy[i].first ) == false && xy[i].second != -1) ) {
puts("No");
return;
}
}
zero.clear();
memset(by, 0, sizeof by);
for( int i = 1; i <= m; ++i )
if( xy[i].second != -1 )
insert_by( xy[i] );
Basis bas_ker;
bas_ker.clear();
for( ll ker : zero )
bas_ker.insert(ker);
for( int i = 0; i < 60; ++i )
if( by[i].second )
bas_ker.insert( by[i].second );
if( bas_ker.size() > bas.size() / 2 ) {
puts("No");
return;
}
Basis bas_x;
bas_x.clear();
for( int i = 0; i < 60; ++i )
if( by[i].second ) {
if( bas_x.insert( by[i].first ) == false ) {
puts("No");
return;
}
if( bas_ker.inside( by[i].first ) ) {
puts("No");
return;
}
}
puts("Yes");
}
}
}
using Check::check;
int main() {
int T;
_w = scanf( "%d", &T );
while( T-- ) {
_w = scanf( "%d", &n );
for( int i = 1; i <= n; ++i )
_w = scanf( "%lld", a+i );
string op;
cin >> op;
if( op == "construct" ) {
construct();
} else {
check();
}
}
return 0;
}