题解：CF1566H Xor-quiz

· · 题解

注意到不考虑异或，每个数 x 都等价于 w(x)=\prod_{p\in P,p|x}p，其中 P 表示质数集。

下面钦定 f,g,h 三个函数的定义域为 \mu(x)\ne 0。

令 f(x)=\bigoplus_{i\in A}[\gcd(i,x)=1]i,g(x)=\bigoplus_{i\in A}[x|i]i,h(x)=\bigoplus_{i\in A,w(i)=x}i，容易得到 f(x)=\bigoplus_{i|x}g(i),g(x)=\bigoplus_{i|x}h(i)，推导就是莫比乌斯反演。因此查询 f 即可推得 h，又因为 \max_{i=100}^{10^6}\dfrac{\sum_{j=1}^i [\mu(j)\ne 0]}{i}<0.65，因此我们可以把 f 全问一遍，这样只需要构造任意满足 h 正确的集合就可以了。

至此，问题转化为：有 m 个集合 S_1,S_2,\cdots,S_m 和长度为 m 的序列 a，选择 T_1\subseteq S_1,T_2\subseteq S_2,\cdots,T_m\subseteq S_m，目标是令 \forall i\in [1,m],\bigoplus_{x\in T_i}x=a_i 且 \sum_{i=1}^m |T_i|=c，给出构造，保证有解。

这个如果直接做只能暴力 dp，但是这个题保证集合随机生成，启发随机化做法。

考虑先构造一个 \forall i\in [1,m],\bigoplus_{x\in T_i}x=a_i 的方案，也就是不考虑集合总大小。这是简单的，对每个集合开一个线性基容易构造。

直觉上解非常多，于是每次我们随机选择集合并随机选 O(1) 个数尝试改变它们的存在状态，同步算出线性基里的数改变的存在状态，计算一下增量，如果与正确大小差更接近就更新方案。

https://codeforces.com/contest/1566/submission/345429158。