codeforces上的dp题（三）

[[ slider_text ]]

[[ item.c ]]

codeforces上的dp题（三）

发布时间 2024-10-23 作者：秋千月 来源：算法小站

dp xor问题

## Codeforces Round 876 (Div. 2)
**[Codeforces Round 876 (Div. 2) D. Ball Sorting](https://codeforces.com/contest/1839/problem/D)**
**问题描述**
给定一个$$1 \sim n$$的排列$$c$$，然后有$$n$$个球排成一排，第$$i$$个球的颜色是$$c_i$$
然后你要重新排序这几个球，使得左边第$$i$$个球有颜色$$i$$
在这个过程中，你可以利用颜色为$$0$$的球，这样的球有$$k \geqslant 1$$个，排序过程有如下决策

1）放置 0 球在任意位置，其他位置保持相对不变
2）选择非 0 球，但是非 0 球是有限制的，非 0 球必须与 0 球相邻，才会被选上
选上之后把它移动到任意位置，花费$$1$$的代价

操作完成之后 0 球消失，同时序列归位，问使得序列归位的最小代价
对$$k = 1 \sim n$$输出答案

### 算法分析
> 什么情况下球必须移动，什么情况下没必要移动？

很重要的一点，**球的相对顺序不会变**
不难发现，这个问题中所需要的额外代价，就是将球归位的代价，什么情况下球不需要归位？
如果有两段形如$$[1, 2, 3]\cdots [7,8,9,10]$$，那么这两段内部是不需要任何操作的
我们要做的是把这些**连续的段**比如$$[3, 4]\cdots [7,8,9] \cdots [5, 6]$$完整地找出来，然后尝试**拼接**

> 假设有若干完整的段，怎么拼接？拼接的代价是多少？

其中在哪一段加入$$0$$，可以理解为暂时删除这一段，然后拼接左右两边
![](/media/content_img/CF876D.png)

> 注意，这里采用的是归位操作，而不是交换操作，二者有什么不同

如图所示，拼接左右两段`[1, 2, 3] and [5, 6]`的时候，我们还可以同时把中间的段**归位**
也就是说，`[x x x x], [7, 8, 9]`这些数之后都会在**正确的位置上**（相对位置）
之后不需要额外操作这些数了，所以这样的 dp 是**无后效性的**

> 具体怎么转移的呢？对于每一个位置，我们考虑它要**拼上哪一段？**

假设当前考虑$$i$$这个位置，枚举$$< i$$的位置$$j$$，其中必须满足$$a_j < a_i$$
然后枚举$$k$$，表示已经用了$$k$$个$$0$$球

1）若$$i$$打头的这一段不发生拼接，$$dp(i, k) \leftarrow dp(i-1, k)$$
2）若$$i$$打头的这一段发生了拼接，枚举拼接位置$$j, j < i, a_j < a_i$$
     $$dp(i, k) \leftarrow dp(j, k-1) + (i-j-1)$$
	 
3)  边界情况，一整段都不需要修改，这个时候我们加一个哨兵节点，$$a_0 = 0, a[n+1] = n+1$$
那么递推到$$n+1, dp(n+1, k)$$就是答案

> 总结，排列的还原问题

**还原排列**，这是一个比较常见的问题
1）排列可以看成若干个**单调递增的段的拼接**，段的内部是单调递增的，但是段与段之间不一定
把单调递增的段称为**递增段**，其余段称为中间段
2）还原排列的时候，尝试把小的递增段拼接成大的递增段
一旦拼接完成，**剩下元素的位置是固定的，插空放入**

## Codeforces Round 976 (Div. 2)
**[Codeforces Round 976 (Div. 2) D. Connect the Dots](https://codeforces.com/contest/2020/problem/D)**
**问题描述**
一条直线上给你$$n$$个点，这些点一开始是孤立的，接下来进行$$m$$次操作
每次操作选三个数字$$(a_i, d_i, k_i)$$，把$$a_i, a_i+d_i, a_i+2d_i,\cdots, a_i+k_id_i$$这些点两两连边
问你连完之后，连通块的个数

### 算法分析
对线段$$[a_i, a_i+k_id_i]$$排序，考虑以下几个值
非孤立点个数`found`，孤立点个数`single`，有几个合并成的连通块`group`
其中`single = n - founds`

扫描的时候维护当前连续的，最长的$$[L, R]$$
1）如果线段之间不重合，假设说有$$l_i > R$$，那么`group += 1, founds += (k[i] + 1)`
同时$$[L, R] \to [l_i, r_i]$$

2）如果线段之间发生重合，首先很明显有$$R = \max(R, r_i)$$
关键要解决的问题是什么呢？对于当前的段$$i$$，**它可能和之前若干个线段重合**
假设$$seg_i$$和$$seg_j$$重合，重合几个点？这是要解决的

> 这些重合的段满足什么条件？

首先，有$$a_j + p\cdot d_j = a_i + q\cdot d_i$$，并且如果有若干重合的点
那么假设$$d_j < d_i$$，我们有$$d_j \mid d_i$$
注意到$$d$$很小，假设我们当前考虑$$d_i$$，能不能枚举？
枚举一下能够$$d \mid d_i$$的$$d$$，有多少个？就是这样的$$d$$，对应几个线段$$[a, a+kd]$$？

直接暴力用`seg[d]`来保存所有的$$[a, a+kd]$$，复杂度是$$O(n^2)$$的，这里可以用数据结构优化

不难想到并查集，如果我们对$$[a, a+kd]$$这个段中的每个点都执行合并
那么会有大量重合的点，我们要使得每个点只被合并一次，注意到点和$$(a, d)$$的值密切相关
而点重合的条件$$a_j + p\cdot d_j = a_i + q\cdot d_i$$，这个表达式
我们枚举$$d = d_j$$，那么有$$a_j \equiv a_i (\bmod d)$$，这样就可以设计出如下算法

预处理所有的段，已经出现的$$d_i, a_i \bmod d_i$$，用集合$$seg(d_i, a_i \bmod d_i)$$维护起来
然后枚举$$d$$，枚举每个$$a_i$$，在`seg[d][a(i) mod d]`集合中的这些线段，
可能会有重合的点，排序后，找出最大的连续段`[L, R]`
`for (x = L; x <= R; x += d)`并查集合并这些段，每合并一个数，`res -= 1`（`res`一开始等于$$n$$）
这样每个`d`都只被合并了一次，答案就是`res`

## Educational Codeforces Round 159
**[Educational Codeforces Round 159 D. Robot Queries](https://codeforces.com/problemset/problem/1902/D)**
**问题描述**
机器人在二维平面上移动，`U, D, L, R`四个方向，以字符串形式给出移动序列
给你$$q$$个询问，每个询问`x, y, l, r`，问你**翻转**移动序列`[l, r]`之后
机器人会不会经过$$(x, y)$$点，一开始机器人都在原点$$(0, 0)$$，每个询问是独立的

### 算法分析
> 首先不考虑$$[l, r]$$区间翻转怎么做？

实际上可以预处理，按照操作序列，遍历每一个点，正着做一次，再倒着做一次
记录每个点最早被访问的位置$$fst_x$$和最迟被访问的位置$$lst_x$$
如果$$fst_x < l$$或者$$lst_x > r$$，那么这个点肯定会被访问

> 那么考虑在翻转$$[l, r]$$之后，访问某个点$$x$$

注意到，机器人在$$[l, r]$$之间的操作，只和$$\Delta x, \Delta y$$有关，考虑暴力做法
**线段树维护区间的每一个后缀对应的**$$\sum (\Delta x), \sum (\Delta y)$$
我们可以考虑将二元组$$\left(\sum (\Delta x), \sum (\Delta y) \right)$$**挂载**到线段树节点$$p$$中

注意查询的时候，不能一边在线段树上找区间$$[l, r]$$，一边查找$$(\sum \Delta_x, \sum \Delta_y)$$
这样一次的复杂度是$$O(\log^2 n)$$，可能会超时

实际上，我们可以先查询，线段树中表示$$[l, r]$$的是哪些节点？把这些节点编号从小到大存下来
一开始我们考虑走到的位置是$$(px\_{l-1}, py\_{l-1})$$，然后走序列中$$[l, r]$$这一段，能否走到$$(x, y)$$？

按编号`id`从小到大遍历$$[l, r]$$的代表区间，区间维护如下信息
一个是**一整段区间和**$$\sum dx, \sum dy$$
还有一个是区间中可能出现的所有**后缀和**，这个用一个`set`维护，便于后续二分查找

在编号`id`的区间中，二分查找是否存在二元组$$(x - px\_{l-1}, y - py\_{l-1})$$
如果存在就直接返回，不存在就让`px += node[id].sx,   py += node[id].sy`
即走完一整个`id`的段后，继续检查下一段

> 尝试找到区间$$[l_i, r_i]$$的时候，返回**线段编号**，需要**倒序处理**

什么意思呢？我们并不直接在线段树上查询，而是将线段编号返回，`if (到了目标区间):  ID.push_back(p)`
那么**先询问右子树，然后再询问左子树**

为什么这样做是对的呢？因为$$[l_i, r_i]$$翻转与否，最后能否走到$$(x, y)$$，取决于$$\sum \Delta_x, \sum \Delta_y$$

翻转之后，从$$(px\_{l-1}, py\_{l-1})$$开始，求$$\sum \Delta\_x, \sum \Delta\_y$$都是针对**后缀和**
并且**先考虑较小后缀，再考虑较大后缀**，所以**优先递归右子树，再左子树**

> 还有没有别的做法？先分析一下性质

注意到在$$l-1$$的位置，不论翻转与否，$$(px\_{l-1}, py\_{l-1})$$是不变的
另外，序列$$[l, r]$$翻转前后，路径是**中心对称的**，同时在终点$$r$$处，$$(px\_{r}, py\_{r})$$一定相同

翻转后，该怎么走，只和$$\sum \Delta_x, \sum \Delta_y$$有关

起点在$$(px\_{l-1}, py\_{l-1})$$处，$$x, y$$方向分别走了多少？
取决于$$[l, r]$$的**某一段后缀**，它的$$dx, dy$$的**和**
并且，$$(px\_{l-1}, py\_{l-1}), (px\_{r}, py\_{r})$$翻转前后都是**相同的**，只有$$[l, r)$$区间内的数会发生变化

翻转后的路径是否能够到达$$(x, y)$$，实际上我们就是要在原路径找一个点$$?$$
使得$$px\_{l-1} + \Delta\_x = ?$$，其中$$\Delta\_x = (px\_{r} - x)$$
即$$px\_{l-1} + (px\_{r} - x) = ?$$

这可以用 STL 快速求解，用`map< pair<int, int>,  int > pos`，预处理每个点出现的位置
比如`pos[ {x, y} ] = i`，对于$$[1, l-1], [r, n]$$这一段的点，按前面的方法暴力判断

对于询问`[x, y, l, r]`，实际上就是问你在`pos`中
是否存在点`( px[l-1] + px[r] - x,  py[l-1] + py[r] - y )`，使得他们出现的位置`>= l 且 <= r-1`
二分查找第一个`>= l`的位置，判断是否`<= r-1`即可

## Codeforces Round 976 (Div. 2)
**[Codeforces Round 976 (Div. 2) E. Expected Power](https://codeforces.com/contest/2020/problem/E)**
**问题描述**
给定长度为$$n$$的两个序列$$a[1\sim n], p[1 \sim n]$$，定义$$S$$是一个多重集
一开始$$S$$是空的
对于每个$$a_i$$，它有$$p_i / 10^4$$的概率被插入$$S$$中，每个元素插入过程是独立的

定义$$f(S)$$，是$$S$$中所有元素的异或和，现在要你计算$$(f(S))^2$$的期望

### 算法分析
不妨先考虑一种$$O(n \cdot 1024)$$的解法，期望 dp，可以考虑**dp 值来表示概率**
那么这个问题就变成签到题了
定义$$dp(i, j)$$表示正在考虑$$i$$（还未决策）这个位置，已经得到的$$S$$集合中的异或和是$$j$$
此时对应的**概率**

那么存在转移
$$dp(i+1, j \oplus a_i) += dp(i, j) \cdot \dfrac{p_i}{10^4}$$
$$dp(i+1, j) += dp(i, j) \cdot \dfrac{10^4 - p_i}{p_i}$$

最后的答案，$$\sum_x dp(n+1, x) \cdot x \cdot x$$
其实是可以冲过去的，需要预处理`mint`的`p[i]`值，$$\dfrac{p_i}{10^4}$$也要提前预处理
这样可以免去算乘法逆元的代价

> 这种做法肯定会被卡，考虑实际上，$$x$$只有10位？能不能从位运算角度来看？

如果一位一位来看，某一位值为`1`的概率是多少？对答案的贡献又是多少？
第$$i$$位为`1`的概率假设是$$P(i)$$，对最终值的贡献是$$2^i$$，那么$$E(f(S)) = \sum\_{i =0}^{9} P(i) \cdot 2^i$$

类似**状态压缩**，对于$$a_i$$，一位一位来看，$$dp(i, j, 0/1)$$表示正在考虑$$a_i$$
当前$$j$$这一位的值是$$0/1$$，此时的概率

那么遍历到$$a_i$$的时候，要`for j = [0...9]`所有的位，枚举当前这一位的值是$$0/1$$
令`x = a[i] 在 j 这一位的值`，有转移$$dp(i, j, 0/1) \cdot p_i \to dp(i+1, j, (0/1) \oplus x)$$
同时也有转移$$dp(i, j, 0/1) \cdot (1-p_i) \to dp(i+1, j, 0/1)$$

计算$$E(f(S)) = \sum\_{j = 0}^{9} dp(n+1, j, 1) \cdot 2^j$$

> 那么$$E(f(S)^2)$$怎么算，$$f(S)^2$$关于**数位**的表达式是什么呢？

不难写出表达式
```math
\displaystyle
f(S)^2 = \left(\sum_{i = 0}^{9} p_i \cdot 2^i \right) \left(\sum_{j = 0}^{9} p_j \cdot 2^j \right) = \sum_{i = 0}^{9} \sum_{j = 0}^{9} p_ip_j \cdot 2^{i+j}
```
定义$$dp(i, p, 0/1, q, 0/1)$$表示正在考虑$$a_i$$，当前$$p, q$$这两位分别为$$0/1$$的概率
转移的话，需要`for p, for q in [0...9]`，$$xp, xq$$分别表示$$a_i$$在这两位上的值

有转移$$dp(i,p,0/1,q,0/1)\cdot p_i \to dp(i+1, p, (0/1) \oplus ap, q, (0/1) \oplus aq)$$
同时 $$dp(i, p, 0/1, q, 0/1) \cdot (1-p_i) \to dp(i+1, p, 0/1, q, 0/1)$$

答案是$$\sum_p \sum_q dp(n+1, p, 1, q,1) \cdot 2^{p+q}$$

## think-cell Round 1 D1
**[D1. Sum over all Substrings (Easy Version)](https://codeforces.com/contest/1930/problem/D1)**
**问题描述**
两个长度都是$$m$$的二进制串$$p, q$$，$$q$$被称为 p-good 当且仅当对于每一个$$1 \leqslant i \leqslant m$$
都存在一个区间$$[l, r]$$满足
$$1 \leqslant l \leqslant i \leqslant r \leqslant m$$
并且在`q[l, l+1, ... , r]`，$$p_i$$是优势的
优势的定义是，$$p_i$$在$$q[l\cdots r]$$中出现的次数$$\geqslant \lceil \dfrac{len}{2} \rceil$$，$$len$$为子串长

对于子串$$p$$，$$f(p)$$定义为在 p-good 二进制串中，$$1$$的个数最小有几个？
对于$$s$$的全部子串，计算$$f$$的和
```math
\displaystyle
\sum_{i = 1}^{n} \sum_{j = i}^{n} f(s_is_{i+1}\cdots s_j)
```

举个例子，$$q$$可以随便选，但是要满足$$q$$是 p-good 的
比如$$f(10)$$，如果让`q = 00`，那么肯定不行，因为此时`p = 10`，`1`此时在`q`中不是众数
如果让`q = 01`，那么是可以的，`q = 10`也是可以的，这两种可能的情况中，$$1$$出现的次数都是$$1$$
所以$$f(10) = 1$$

说明，比如说有一些都是`1`的段，形如`111111`，构造`q`的时候，不需要弄成`111000`
即不一定要考虑一整个段的长度
实际上，只要保证存在一个区间，使得`1`是区间的众数即可，哪怕是最小的区间
比如考虑第$$i$$个位置，`010`也是可以的，因为对于第二个位置的`1`，此时存在区间`[1, 2]`
使得`1`是众数，这也是可以的

### 算法分析
数据范围比较小，可以暴力统计$$s$$的每一个子串，假设考虑子串$$p$$

> 对于$$p$$的某一个位置值是$$1$$，构造 p-good 串，有什么性质？

包含这个$$1$$的某一段区间，假设长度是$$m$$，那么区间中$$1$$的个数至少要$$\geqslant \lceil\dfrac{m}{2} \rceil$$
要最小化$$1$$的个数，在构造 p-good 串的时候，就要使得长度$$m$$尽可能小

那么对于$$p$$中，假设第$$i$$个位置为$$1$$，那么我们尽量只考虑长度为$$2$$的区间$$[i, i+1]$$
让这个区间为`[1 0] or [0 1]`

> 那么选`[1 0]`还是`[0 1]`呢？

注意到，`[1 ?]`和`[0 1] or [1 0]`**总是能够匹配**，不论`?`中是什么数
但是我们填上`[0 1]`后，再填一个`0`，构造出`[0 1 0]`，它就可以匹配形如`[1 ? ?]`的段

遍历$$p$$的时候，一旦出现一个`1`，我们就可以跳过`3`个位置，然后计算`[0 1 0]`的代价

> 这样贪心是最优的，证明如下

存在匹配`[1 ? ?] and [0 1 0]`，当下一个位置再出现一个`1`的时候，需要找最小匹配
`[1 ? ? 1] and [0 1 0 ?]`，对于新加入的`1`，要么选择`[1 ? ? 1] and [0 1 0 1]`
要么就继续是`[0 1 0 0 1 0]`，哪一种更优呢？

首先，对于`[1 ? ? 1]`，新加入的这个`1`，它的代价**不能被忽略**
不管是`[0 1 0 1 ? ?]`还是`[0 1 0 0 1 0]`，都会有这个`1`的代价
但是我们选择`[0 1 0 0 1 0]`，能够继续忽略最后这个`1`往后`3`个位置，显然更优

## think-cell Round 1 D2
**[D2. Sum over all Substrings (Hard Version)](https://codeforces.com/contest/1930/problem/D2)**
### 算法分析
根据上面的分析，可以用** dp 优化**
定义$$dp(i)$$表示以$$i$$**结尾**的子串，对答案（关于串中`1`的个数）的贡献

那么很显然，如果$$p_i = 0$$，那么存在转移$$dp(i-1) \to dp(i)$$

如果$$p_i = 1$$，那么所有以$$i$$结尾的子串，都会加上$$i$$位置的这个`1`
哪些串以`i`结尾？`[1....i], [2....i], [3....i], .......,  [i-1, i], [i]`，一共$$i$$个串
对答案的贡献（关于`1`的个数）多了$$i$$
所以有转移$$dp(i-3) + i \to dp(i)$$（根据上面的分析，我们可以忽略掉连续的`3`个位置）

特别注意，在计算的时候，可能子串长度只有`1`或者`2`，那么不能写成$$dp(i-3)$$转移
写成$$dp(\max(0, i-3)) \to dp(i)$$，如果一个位置为`1`，子串长度即使$$< 3$$，前面的位置仍然可以忽略

## CodeTON Round 5
**[CodeTON Round 5 C. Tenzing and Balls](https://codeforces.com/contest/1842/problem/C)**
**问题描述**
给你$$n$$个球，每个球的颜色是$$a_i$$，其中$$1 \leqslant a_i \leqslant n$$
可以执行以下操作任意次
选择$$i, j$$，满足$$1 \leqslant i < j \leqslant |a|$$并且$$a_i =a_j$$
将$$[i, j]$$的球全部都移走，然后两端拼接，$$j$$下标会减少$$j-i+1$$
问最多能移走几个球？

### 算法分析
这是一个很明显的$$dp$$，$$dp_i$$决策$$i$$这个位置是否消去
如果不消去，那么很显然$$dp(i-1) \to dp(i)$$
否则，我们枚举**和哪个位置一起消去**

维护`pos[ a[i] ]`，表示`[1...i-1]`前缀中所有`a[i]`出现的位置
不妨设`pos[ a[i] ] = {j1, j2, ...., jk}`，那么我们有如下算法，`for i,  for j in pos[ a[i] ]`
有转移$$dp(i) \leftarrow \max( dp(j-1) + i-j+1 )$$，直接做是$$O(n^2)$$的

有几种优化方法，实际上表达式写成$$dp(j-1) - j + (i+1)$$，会变化的只有$$dp(j-1)-j$$
可以考虑**动态开点线段树**，在`tr[ a[i] ]`中，区间查询$$[1\cdots i-1]$$的**最大值**
那么就可以用$$res + i + 1$$来更新$$dp(i)$$
然后再执行单点修改，$$i$$处单点修改成$$dp(i-1) - i$$

当然，因为这里是**前缀最大值**，可以边扫描边维护
直接用$$pos(a[i])$$表示$$a_i$$出现过的位置$$j$$，$$dp(j-1) - j$$最大的那个值
每次遍历的时候，$$dp(i) \leftarrow pos(a[i]) + i + 1$$
然后执行$$pos(a[i]) \leftarrow \max(dp(i-1) - i)$$

## Educational Codeforces Round 155
**[Educational Codeforces Round 155 D. Sum of XOR Functions](https://codeforces.com/problemset/problem/1879/D)**
**问题描述**
给你一个非负的长度为$$n$$的序列$$a$$，需要你计算
```math
\displaystyle
\sum_{l = 1}^{n} \sum_{r = l}^{n} f(l, r) \cdot (r-l+1)
```
其中$$f(l, r) = a\_l \oplus a\_{l+1} \cdots a\_{r-1} \oplus a\_r$$

### 算法分析
首先，不难发现，$$\oplus$$操作是符合前缀和的，可以用前缀和处理任意区间的和
这种区间问题，一般都是考虑用前缀和化简
**枚举$$r$$，然后维护$$l$$相关的信息**，具体来说
```math
\displaystyle
\sum_r \sum_l (S_r \oplus S_{l-1}) \cdot r - (S_r \oplus S_{l-1})\cdot (l-1)，\text{枚举 r} \\
\Rightarrow \sum_{l=1}^{r} (S_r \oplus S_{l-1})\cdot r - \sum_{l = 1}^{r} (S_r \oplus S_{l-1}) \cdot (l-1)
```

> 这样的式子怎么优化呢？

参见**[CCPC Changchun 2020 F, Strange Memory](https://www.ringalgo.com/article/11/)**
这个问题类似，不过更难一点，它要求$$a_i, a_j$$满足条件$$a_i \oplus a_j = val$$
求满足限制的
```math
\displaystyle
\sum_{i = 1}^{n}\sum_{j = i+1}^{n} (i \oplus j)
```
> 这种问题的处理思路是什么呢？**一位一位看**，$$cnt(i, 1)$$表示$$i$$这一位是$$1$$的数的个数
那么第$$i$$位对答案的贡献是$$ans += cnt(i, 1) \cdot 2^i$$
回到这个问题，可以记$$cnt(val, j, 0/1)$$表示值为$$val$$，第$$j$$位是$$0/1$$的数有多少个

这个问题同样也可以按位来考虑
```math
\displaystyle
S_r \oplus S_{l-1} = \sum_{i=0}^{30} [S_r(i) \oplus S_{l-1}(i) = 1] \cdot 2^i
```
从而表达式可以写成
```math
\displaystyle

\sum_{i = 0}^{30} 2^i \cdot \left( \sum_{l=1}^{r} [S_r(i) \oplus S_{l-1}(i) = 1] \cdot r - \sum_{l=1}^{r} [S_r(i) \oplus S_{l-1}(i) = 1] \cdot (l-1) \right)
```
**遍历$$r$$**的时候，用$$cnt1, cnt2$$分别维护两个$$\sum$$的值
记$$cnt1(i, 0/1)$$表示前缀$$[1\cdots r-1]$$中，第$$i$$位是$$0/1$$的个数

这样统计的时候，$$x = a_r \gg i \ \textbf{and} \ 1$$
若$$x = 1$$，那么取$$cnt1(i, 0)$$，否则就取$$cnt1(i, 1)$$，也就是说
计算的时候第一部分取$$cnt1(i, x\oplus 1) \cdot r$$

第二部分相当于是$$\bigoplus\_{j = 1}^{r} S_j \cdot j$$，可以直接维护，这部分答案是$$cnt2(i, x \oplus 1)$$

然后更新$$cnt1, cnt2$$，`for i = [0, 30]`所有的位，令$$cnt1(i, x) += 1$$，$$cnt2(i, x) += i$$

> 另外还有一类型的异或问题，求$$\bigoplus x$$值第$$k$$小之类的
都可以先把$$a[1\cdots n]$$插入一棵 01-Trie 中，然后一位一位看
在 01-Trie 中，从 root 到叶子结点，每走一层深度，相当于从高位往低位遍历了一位
优先考虑能不能往$$0$$走，也就是说往$$cld(x_j)$$走（$$x_j$$表示$$j$$这一位的值）
如果可以，那么这一位对答案没有贡献
否则，这一位的异或结果就一定是$$1$$，那么必须往$$cld(x_j \oplus 1)$$走

**特别注意**，这个问题中，$$cnt1(i, 0/1), cnt2(i, 0/1)$$的初始值如何维护？
一开始的时候，可以认为集合中只有$$0$$这个数，那么$$i \in [0, 31]$$这些位上，都是$$0$$
所以这些位$$cnt1(i, 0) = 1$$
另外，因为一开始$$l = 1$$，但是$$[S_0(i) = 1] \cdot (l-1) = 0$$，$$cnt2$$的初始值仍然是$$0$$

上一篇：codeforces上的dp题（二）下一篇：codeforces上的dp题（四）

看完文章有啥想法