2024-08-05 训练总结

乐！

一切大师

计数题，然而不会推式子，但是乱搞了一个 \(n\ln n\) 的做法。

你考它干嘛

又是钻研一道题废掉一整场的比赛，还是没有吸取教训。

但是我还没改出来。

digital

构造题，一看就会，模拟归并排序就可以了。

感觉要减少心中对构造体的恐惧，我可以的！

代码之神 小Y

原题：P7620 CF1431J Zero-XOR Array - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

感觉做完之后对数位 dp 的理解更加深刻了。

其实也不能算作数位 dp。就是我们可以将情况分为四种：

1. 只有 \(L\) 限制
2. 只有 \(R\) 限制
3. 都有限制
4. 都没有限制

赛时我只想到 \(4^n\) 的，其实可以优化。

前面两个不优化，第三个发现只有一种取值，答案是固定的，可以看作只有 \(L\) 限制。第四个我们发现如果有 \(i\) 是满足都没有限制的，答案为 \(\prod_{i\neq j} w_j\)，\(w\) 表示取值方案数。

可以这么理解：如果有 \(L_{n}=0,R_{n}=2^m-1\)，也就是可以随便取，那么答案就是 \(\prod_{i=1}^{n-1} (R_i-L_i)\)，因为对于所有的取值方案，\(n\) 一定只有一种方案可以满足异或值为 \(S\)。（这个思想同样用在：P3791 普通数学题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）

然后就 dp 一下就可以，可以看题解回想一下。