格雷码 && CF1848F. Vika and Wiki 题解-526互联

格雷码 && CF1848F. Vika and Wiki 题解

本来有个GitHub上的Hexo博客的，但是我用起来不太熟练……先在博客园里写了后到时候转移过去吧。

前置知识：格雷码（了解的读者可以跳过）

格雷码是所有k-bit（含k个二进制位）的数的一个排列，使得两个循环相邻（即两相邻或分别位于首尾）的数在二进制表示下有且仅有一位不同。但是这么描述的话排列不是唯一的，因此我们取以以下方式构造的k位格雷码以保证唯一性，下文同：

构造出(k-1)位的格雷码（特别的，当k=1时我们认为0位格雷码是空串）；
k位格雷码的前 \((2^{k-1})\) 位分别为(k-1)位的格雷码按顺序依次在最高位前加上0后构成的k-bit的数；
k位格雷码的后 \((2^{k-1})\) 位分别为(k-1)位的格雷码的颠倒顺序在最高位前加上1后构成的k-bit的数。

下文记k位格雷码编码操作（即将每个k-bit数x对应到格雷码所对应排列中的第x个（数学对象的下标从0开始，下同）的一一映射）为 \(G_k(x)\) 或 \(G(x)\)。

直接按上文生成是 \(\Theta(\sum_{i=1}^k i2^i)\) 的（~~不知道是 \(\Theta(k2^k)\) 还是 \(\Theta(k^22^k)\) 的，总之懒得求和了~~）则 ~~通过打表~~ 可以发现一个 \(\Theta(k)\) 的计算公式：

\[G(x)=x \oplus \lfloor \frac x2 \rfloor \]

证明可以考虑由数学归纳法证明两条性质之一时顺便推出来：

x所有位翻转（\(\oplus (2^k-1)\)）相当于 \(G(x)\) 最高位翻转。
x的某一位翻转相当于 \(G(x)\) 的这一位和更低一位（如果有）翻转。

这个式子有多种含义：

首先是最表面的数值含义，即格雷码编码可以通过一个数异或其除以二下取整的结果来计算。
若将x看成一个std::bitset<k>的话，那么就相当于把这个std::bitset异或上自己往低位右移一位后的结果。
然后再分开考虑每一位来看，则可以发现 \(G_k(x)_i=\begin{cases}x_{i+1}\oplus x_i&i<k-1\\x_i&i=k-1\end{cases}\)。
由上式可以发现，格雷码编码操作可以看成对位数组的异或差分操作（对于熟悉stl的读者的解释：如果x是一个 按大端序（最高位在前） 存储二进制位的std::vector，则相当于[std::adjacent_difference](std::adjacent_difference - cppreference.com) (x.begin(),x.end(),x.begin(),std::bit_xor<>())）。

由此不难理解格雷码的解码操作：解码操作为编码操作的逆，编码操作是差分，解码操作肯定就是前缀和了。\(G^{-1}(x)=\bigoplus_{i=0}^{k-1}\lfloor \frac x{2^i} \rfloor\) （\(\bigoplus\)表示异或和，也可以用U+2A0A ⨊），可以理解为将第i位以及更高位累加到结果的第i位上。

例题

P5657 [CSP-S2019] 格雷码

模板题，略。

CF1163E. Magical Permutation

题意：存在一个集合S（值域 \(\text{SIZE}\le2\cdot 10^5\)），一个整数x是好的当且仅当存在一个 \([0,2^x)\) 内所有整数的排列使得相邻两个整数的异或值在集合S内。求最大的好的整数并构造出排列。

Sol：不失一般性地，不妨设排列第0位是0。由于 \(x\le \log |\text{SIZE}|+1\)，所以我们依次枚举x进行。首先，显然在考虑x是否是好的的时候集合中 \(\ge 2^x\) 的数肯定是没有的可以去掉（然后记剩余的数构成的集合是 \(S_x\)）。然后不考虑“相邻两个整数的异或值在集合S内”的限制，考虑怎么样用S中数的异或组合（即S某个子集的异或和，类似于线性代数中的线性组合概念）表示出 \([0,2^x)\) 内所有整数，这样。求出一组S的极大线性无关组（用线性基依次尝试插入，不过一定要注意插入后要在当前行记录下当前行的原始0-1向量（即二进制位向量，下同；用k维0-1向量、长度为k的0-1数组、k-bit整数来表示是等价的），因为线性基的插入操作会存储改变了的向量，而题面中要求原向量），不妨设为\((S_{x,0},S_{x,1},\dots,S_{x,r-1})\)，并将0-1向量 \((\lambda_0,\lambda_1,\cdots,\lambda_{r-1})\) 称为在基 \((S_{x,0},S_{x,1},\dots,S_{x,r-1})\) 下 \(\bigoplus_{i=0}^{r-1}\lambda_iS_{x,i}\)（两者进行向量点乘后的结果，可以理解为把所有 \(\lambda_i=1\) 的 \(S_{x,i}\) 取出来的异或和）的坐标。则首先当 \(r\lt x\) 时无法表示 \(2^x\) 内所有数，显然无解。当 \(r=x\) 时，我们发现 \(2^k\) 个中的每一个 \(k\) 维0-1向量都与 \(2^k\) 个坐标中的某个坐标不重不漏地一一对应（如果还是不理解的，该线性变换的单射性在LOJ#114. k 大异或和中也有应用，这里就不多讲了可以自己BDFS一篇题解并按照其过程理解为什么可以这么做而不会重复计数）。

于是，我们就可以取所有 \(k\) 维0-1坐标对应的向量，然后就满足题目中说的 \([0,2^x)\) 内所有整数的排列的要求。然后我们就需要让每对循环相邻的数的异或值在基底里（原题要求是每对相邻的数的异或值在 \(S_x\) 里，但以下会说明我们加强限制条件后仍一定有解），也就是每一对循环相邻数在基底下的坐标都有且仅有一位不同。仔细想想可以发现这就是格雷码。于是按格雷码顺序输出每个坐标对应的0-1向量即可。

由于 \(\log(a_i\oplus a_{i-1})(i=1,2,\cdots,2^x-1)\) 依次为 \(0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,\cdots\)（用格雷码的本质意义是差分这个性质很好理解），所以也可以用类似于DFS中序遍历完全二叉树或对 \(i=1,2,\cdots,2^x-1\) 依次取lowbit的方式构造出两相邻格雷的异或值。

双倍经验：P7949 [✗✓OI R1] 左方之地

构造一个 \([0,2^n)\) 内所有整数的排列，使得相邻两整数的异或值二进制表示下恰好包含k个1。\(n,k\le20\)。

题面的限制更简单了，难度也由紫变蓝了，但是更诈骗了，比赛时只过了暴力和k=1（起提示性的普通格雷码）或n-1的部分分。

一般做法就是所有n位的popcount为k的数插入线性基，若最后基的大小<n则无解（或者判断当 \(n \ge 2\) 时当且仅当k为奇数且 \(k<n\) 才有解然后自己构造n个基的元素，参考AtCoder官方题解的构造方式的Line 286），否则就和上题一样的处理方法。

三倍经验：

和P7949完全一样，不过不卡常。

JSCPC 2022 H. Super Gray Pony

注：可以打开官方题解作为补充。

简要题意：求一个n-bit整数迭代进行k次格雷码编码（记为 \(G^k(x)\)，下同）操作后的结果。\(n\le 3\times10^6,k\le10^9\)。

法1. 考虑 \(G^{2^l}(x)=x\oplus \lfloor\frac{x}{2^{2^l}}\rfloor\)（证明考虑数学归纳法），也就是说当 \(k=2^l\) 时每一位都只会贡献至多两个位置（当前位和比它底 \(2^l\) 位的位）。因此类似于快速幂那样将k拆成二进制位后对为1的位执行 \(x\larr G^{2^l}(x)\) 操作即可。注意到只涉及异或、右移、赋值操作，用std::bitset优化。注意到 \(2^l>n\) 时操作可以忽略（~~然而优化不了多少~~），时间复杂度 \(\Theta(\frac{n\log n}w)\)。

法2. 由于格雷码的本质是差分，关于差分我们有一个结论，打开《具体数学》第二版中译版p. 156/英文版p. 187，就可以发现 \(\Delta^kf(x)=\sum_i \binom ki (-1)^{k-i}f(x+i)\) 这样一个公式（当然这是加减法的差分，对于0-1序列的差分我们有个更简单的形式：\(\Delta^kf(x) \mod 2=\bigoplus_i (\binom ki \mod 2)f(x+i)\)）；因此我们因此当一个数的更高位上有足够多位时（不足的话等价于补0），有 \(G^k(x)_i=x'_i=\bigoplus_m (\binom km \mod 2)x_{i+m}\)。由卢卡斯定理将组合数拆位得， \(\binom km \mod 2\) 的值当且仅当 \(m\sube k\) 时为1否则为0。又发现这个式子是个差卷积的形式，所以直接NTT可以\(O(n\log n)\) 搞~~然后被std::bitset吊打~~。

双倍经验：CF1848F. Vika and Wiki

法1. 二分。判定同上一题，不赘述。

法2. 按位贪心/倍增。

我一开始还在纠结命名问题……后来才发现其实倍增也可以看作位运算题的逐位确定的通法的一种例子。

类似于上一题法1的做法和倍增求lca的做法，依次尝试 \(n/2,n/4,\cdots,1\)，如果迭代这么多次后仍不全为0那么就真的迭代，否则就原地不动，然后找到最后一个含1的数组，再迭代一遍就变全0。注意一开始就全0的要特判。这么做是 \(\Theta(nw\log n)\) 的，不过发现由在倍增到 \(2^l\) 时再迭代 \(2^l\) 次一定变全0（因为总共迭代了n次），也就是说此时原串变为循环节为 \(2^l\) 的周期串了，因此可以只用保留一段循环节（具体可以每次倍增后砍掉右边部分只留左边），可以做到理论最优复杂度 \(\Theta(nw)\)。

Code:

signed main(){
	int n=g90;
	// int K=std::__lg(n);
	vi a(n);
	// a[n-1]=1;
	// for(int k=1;"GTRAKIOI!";++k){
		// std::cout<<"Phase "<<k<<'\n';
		// vi tmp(n);
		// for(int i=0;i<n;++i)tmp[i]=a[i]^a[(i+1)%n];
		// a=tmp;
		// for(int i=0;i<n;++i)std::cout<<a[i]<<' ';
		// std::cout<<'\n';
    	// if(std::none_of(all(a),[](int x){return x;}))break;
	// }
	for(auto&x:a)x=g90;
	if(std::none_of(all(a),[](int x){return x;})){
		puts("0");
		return 0;
	}
	int ans=0;
	for(int of=n/2;of;of/=2){
		vi tmp(n);
		for(int i=0;i<n;++i){
			tmp[i]=a[i]^a[(i+of)%n];
		}
		if(std::any_of(all(tmp),[](int x){return x;})){
			ans|=of;
			a=tmp;
		}
	}
	printf("%d\n",ans+1);
}

法3. 高维前缀和。

注意到当i=0时这个式子就是一个高维前缀和/子集和变换/Zeta变换（Or卷积时做的那个变换），且若一开始不全为0则在清零的前一刻一定有 \(x_i\) 全为1，即最后一个满足 \(G^k(x)_0=1\) 的k的下一刻就是清零，所以直接贴上高维前缀和板子就行了。