比赛链接
Result
Cloudflare 发力了！！！
D题人机验证一直在卡，然后又就丢掉写 E 去了，于是忘记还有道题没交，然后 \(ans\) 初始值设小了；F 题提交的时候人机验证卡了 10min，不然应该能调出来……
Solution
D - Minimum XOR Path
\(2^{60} > 10^{18}\)
E - Min of Restricted Sum
对于所有 \(X_i,Y_i\) 建图，容易发现每一位、每一个连通块的答案都不相关。那么当连通块和二进制位固定时，确定一个值则确定了所有值。所以可以枚举连通块中一个点的数值，直接算最小值即可
code
F - Rotated Inversions
好题
画个数轴推一下可以发现（令 \(i<j\)）：
- \(a_i<a_j\)：在 \(m-a_j\le k<m-a_i\) 时对答案有贡献
- \(a_i>a_j\)：在 \(0\le k<m-a_i\) 或 \(m-a_j\le k < m\) 时对答案有贡献
- \(a_i=a_j\)：对答案一定没有贡献
这是我们就可以结合差分 \(O(n^2)\) 求解了。但这是可以发现在修改差分数组时，两种情况的操作几乎一样，只有 \(a_i>a_j\) 时 \(d_0\) 要 \(+1\)。那么差分数组可以变成：\(d_0\) 为原序列逆序对数，其他位置都在 \(a_i\ne=a_j\) 时可以被修改。这就好写很多了
code
G - Flip Row or Col
好题
因为 \(m\le 18\)，我们从这个方向考虑。令 \(a_i\) 为第 \(i\) 行表示的二进制数，对于每一行或列操作一次以上时没有意义的。令对于列的操作次数表示的二进制数为 \(x\)，\(a_i\) 最后一定是 \(a_i\oplus x\) 或 \(a_i\oplus x\) 取反。记 \(f_i=\min\{\text{popcount}(i),m-\text{popcount}(i)\}\)
那么 \(ans_x=\sum\limits_{i=1}^{n}f_{a_i\oplus x}=\sum\limits_{i=0}^{2^m-1}cnt_if_{x\oplus i}\)。可以惊奇的发现这是异或卷积的形式！即 \(ans=x\times f\)，其中 \(\times\) 为异或卷积。直接上 FWT 板子即可
code