T4

20 分

暴力搜索不是 $0$ 的位置的值，然后用组合数计算一下加上 $0$ 的方案数，复杂度是拆分数级别的。

40 分

写一个简单 dp 就行，复杂度 $\mathcal{O}(nr^3)$。

$n=2$

本质上是要求 $\sum_{i=0}^r [l\le (i+ i\oplus z)\le r]$。

考虑在二进制下使用数位 dp 解决问题，如果从高位向低位 dp，很难满足两数之和在 $l\sim r$ 之间这个限制。

在此之前先解决一个问题，如何从低位到高位比较大小？（判断一个数是否大于等于一个已知的数 $x$）

可以用一个 $tag$ 来维护，$tag=1$ 表示在这个数最低的前 $i$ 位时大于等于 $x$ 最低的的前 $i$ 位。

现在新增一位，如果这个数新增的这一位大于 $x$ 新增的这一位，那么 $tag$ 一定为 $1$。

如果相等，则 $tag$ 的值不变，即看最低的前 $i$ 位比较结果。

如果 这个数新增的这一位小于 $x$ 新增的这一位，那么 $tag$ 一定为 $0$。

于是就可以从低位向高位 dp，枚举当前这一位填不填，有没有进位，就可以做到 $\mathcal{O}(\log r)$ 的复杂度。

正解

其实跟 $n=2$ 差不多，无非是有没有进位变成了进位是多少，每次转移枚举 $A$ 中有多少个数当前二进制位为 $1$。

时间复杂度 $\mathcal{O}(n^2\log r)$。