【每日一技·1】数值倍增法：HDU 多校 2024 R10 1010 & CF1844G

**【已经收入文章《[每日一技](/article/8xv5xva5)》。】**

**UPD 20241120: 添加了一道习题。**

前言：这篇文章包含两道题的题解，以及相同的一个 trick（我称其为“数值倍增法”）但是只投到了 CF1844G 上面。既然 1844 里有 844 作为子串，那么我是不是也要学习一下 844 的卷批精神呢。

## HDU 多校 2024 R10 1010

#### 题意

给定两个长度为 $q$ 的数列 $a,b$，求一个字典序最小的数列 $x$，满足下面条件：

- $(x_{(i+q-2)\bmod q+1}\oplus a_i)+(x_{(i+q-2)\bmod q+1}\oplus b_i)=x_i$

$1\le q\le 3\times 10^5,0\le a_i,b_i<2^{32}$。

#### 题解

这题一看发现询问的加密是循环的，好像不可做。但是可以用我们的“数值倍增法”思考。下面就以这题为例介绍一下“数值倍增法”。

考虑观察这个操作的本质，发现只有异或和加法。寻找共同点，发现异或和加法都不改变奇偶性。因此在模二意义下，$x+y\equiv x\oplus y$。

因此我们可以一位一位从低到高求答案。在模二意义下改写题目式：$x_j+a_i+x_j+b_i\equiv x_i\pmod 2$。发现无论 $j$ 是多少，$x_i\equiv a_i+b_i\pmod 2$ 恒成立。因此我们有了 $x_i$ 的最低位。

继续往下推，发现只有 $x_j$ 的最后一位才能影响 $x_i$ 的第二位，因此我们可以类似地把 $x_i$ 的第二位推出来，还是不出现循环；以此类推，所有的 $x_i$ 的每一位都能求出。这题就做完了。

复杂度 $\Theta(n\log n)$，一句话总结就是拆位破循环。

#### 习题

- [CF1634B](https://www.luogu.com.cn/problem/CF1634B)，请在看完题十秒内想出，自己计时。

## CF1844G

#### 题解

题意都能看得到，略；建议先看看上题的题解来了解一下“数值倍增法”。

考虑“边权”不好处理，那么我们以 $1$ 为根处理 $\text{dis}(1,i)$，然后简单差分相减求出边权。那么怎么求出 $\text{dis}(1,i)$ 呢？

我们记 $d_i=\text{dis}(1,i)$（题目里给的数组记为 $a_i$），那么我们有 $a_i=\text{dis}(i,i+1)=d_i+d_{i+1}-2d_{\text{lca}(i,i+1)}$。看起来这就没法做了。

考虑“数值倍增法”。对于最低位，$a_i\equiv d_i+d_{i+1}\pmod 2$！因为 $d_1=0$，所以我们能把所有的 $d_i\bmod 2$ 都求出来。接着同样发现 $a_i\equiv d_i+d_{i+1}-2d'_{\text{lca}(i,i+1)}\pmod 4$，其中 $d'_x=d_x\bmod 2$。那么同样能够求出 $d_i\bmod 4$。以此类推，$d_i$ 的所有位也都能求出来。

注意特判无解的情况；且 $d_i$ 最大可能到 $60$ 位（$\sum a_i$），不能开小了。

#### 习题

- [qoj9479](https://qoj.ac/problem/9479)（我非常喜欢的一道题）

正在渲染内容...