菜王的 blog

我寻思这种“一正常题非要爆改计数嗯堆难度结果整出一托答辩”不应该是模拟赛恰烂钱才能干的事吗，怎么扔 CF 了。真不如来做我们 P11269 爆改版。

考虑 E1 咋做。先考虑快速算出 $\textrm{SG}(a, x)$。如果直接打表你会寄。所以在函数的原本意义上先做一些操作。可以发现，我们只需要保留 $a$ 中 $x$ 上为 $1$ 的那些位，其他位的信息我们可以移动到那些位上。

假如 $a$ 中有一位为 $1$ 且 $x$ 中那一位为 $0$，那么我们可以将这位扔掉，并将 $a$ 在 $x$ 中更低的 $1$ 位上都赋为 $1$。那么 $a$ 只在 $x$ 中有值的位上有值，并且我们并不关心 $x$ 中有值的位具体是哪些，所以我们可以将其平移到最前面，那么 $x$ 就变为了 $2^k - 1$ 这样的数。更进一步的，我们可以将 $a$ 最高位之后的位都扔掉，那么新的 $x$ 最高位和 $a$ 的最高位相等，于是 $\textrm{SG}(a, x)$ 一定能被转化成 $\textrm{SG}(a', 2^k - 1)$，其中 $k$ 为 $a'$ 最高位，设其为 $G(a')$。

那么我们对 $G$ 打表，规律就显而易见了：我们有：

$G(n) = \begin{cases} 0 & n = 2^k - 2 \ (k > 0)\\ k \oplus 1 & n = 2^k\\ \lceil\log_2 n\rceil & \mathrm{otherwise}\\ \end{cases}$

那么我们就以 $O(n \log_2 v)$ 解决了 E1。

考虑解决 E2。由于上述结论，$\mathrm{SG}$ 值显然是 $O(\log_2 v)$ 的，那么我们只要算出每堆石子取到每种 $\mathrm{SG}$ 值的方案数，那么就能 $O(n \log_2^2 v)$ 合并出最终的答案。

观察计算 $\mathrm{SG}$ 值的代码：

inline int SG(int a, int x){bool flg = 0;int s = 0;
	for (int i = 29;i >= 0;i --){
		int aa = a >> i & 1, xx = x >> i & 1;
		if (!xx) flg |= aa;
		else aa |= flg, s <<= 1, s |= aa;
	}
	if ((s + 2 & s + 1) == 0) return 0;
	if ((s & s - 1) == 0) return __lg(s) ^ 1;
	return __lg(s) + 1;
}

我们发现，我们只关注 $flg, \log_2 s$ 以及 $s$ 是否为 $2^k - 2, 2^k$ 形式，并且我们所做的操作就是根据 $aa, xx$ 的取值来往 $s$ 的后面加一位。

那么我们考虑建出一个识别 $01$ 串的自动机，只需要识别 $1000\cdots0$ 以及 $111\cdots10$ 两类串，显然这个自动机只有常数个节点。

这样就可以数位 DP 了：从高到低考虑 $x$ 的每一位，那么我们需要记录；

• 当前考虑到哪一位；
• 是否顶到 $b$ 的上界；
• $flg$ 的值；
• 走到了自动机的哪个节点；
• 串中第一个 $1$ 与串尾的距离。

显然可以枚举这位选 $0$ 还是 $1$ 来做到 $O(1)$ 转移。对于单个数求方案数就是 $O(\log_2^2 v)$ 的。那么总时间复杂度就是 $O(n \log_2^2 v)$。代码非常好写，E2 喜提 CF 最短解。

E1 代码，E2 代码。