D. Taiga's Carry Chains
见代码注释部分即可，关键点在于如何考虑状态转移。
还有容易出错的地方是最后的答案计算，不能用 \(max(f_{30,k,0}, f_{30,k,1})\) 作为最终答案，因为对于 \(f_{i,j,k}\)，只会考虑低 \(i\) 位部分的进位贡献，但更高位也有可能产生进位贡献。考虑这个情况：\(n=2^{30}-1\)，\(k=3\)；第一次操作在第 \(0\) 位，此后最高位 \(1\) 就不在低 \(30\) 位中了，后面两次操作的贡献无法累计。因此，需要枚举对低 \(30\) 位共操作了多少次，剩下的进位只会在高于低 \(30\) 位的位置产生，并且这时 \(n\) 一定是 \(2\) 的次幂，每次操作恰好产生一次贡献。
code
E. Shiro's Mirror Duel
题目给定最大询问次数为 \(2.5n + 800\)，并且本题还涉及到概率。那么我们可以推测本题的期望询问次数是 \(2.5n\)，我们也只需要给出一个期望解即可。
（这里不再详细说明为什么要想到这么做，而是更偏向于解法的期望正确性证明，因为我觉得后者更重要一些）
回顾交换操作：询问 \((x, y)\)，会有 \(\frac{1}{2}\) 的概率交换 \((p_{x}, p_{y})\)，另外 \(\frac{1}{2}\) 的概率交换 \((p_{n-x+1}, p_{n-y+1})\)。
整个解法分为两步：第一步，尝试将所有 \(x + y = n + 1\) 的数 \((x, y)\) 交换到对称的位置上（只要求对称即可，不一定要到最终的目标位置）。我们可以发现，对于每一对 \((x, y)\)，\(1\) 次操作一定可以达到目的：只需要交换 \(pos[x]\) 和 \(n - pos[y] + 1\) 两个位置上的数，无论最终是哪种交换，一定能够保证交换后 \(x, y\) 对称。特殊地，\(n\) 是奇数时，需要保证先将 \(\frac{n+1}{2}\) 交换到中间位置。
第一步后，对于 \(\forall x + y = n + 1\) 的 \((x, y)\)，二者一定在序列中对称。接下来进行第二步：尝试将每一对 \((x, y)\) 交换到它们的目标位置。例如：\(p = [2, 1, 3, 5, 4]\)，我们现在想要将数字 \(1,5\) 交换到第 \(1,5\) 个位置，暴力即可，根据概率大概只需要个位数次。
交换过程如下图所示，通过概率计算可知，将数字 \(1,5\) 复位的期望操作次数为 \(4\)。
共有 \(\frac{n}{2}\) 对数字需要复位，因此第二步中的期望操作总次数为 \(2n\)；在第一步中，每一对数字只需要操作一次，共 \(\frac{n}{2}\) 次。因此，上述算法的总期望操作次数为 \(2.5n\)，恰好满足限制。
code