【安徽集训】Entropy

出题人罗哲正是神爷 Orz

Description

这是一道披着交互题外衣的通信题，只支持 C++。
你需要实现 \(2\) 个函数。
交互库先给第一个函数传入一个参数 \(n\)，你加密得到的 \(01\) 字符串的长度必须是 $n。你需要根据 \(n\) 做一些相应的预处理，并向交互库返回你能接受的最大 \(\text{long long}\) 类型整数 \(m\)。
先根据你返回的 \(m\) 给分。若 \(m_{you}\gt m_{ans}\) 则你得 \(0\) 分，若 \(m_{you}=m_{ans}\) 则你得 \(100\) 分，否则你得 \(0.5\frac{\ln{m_{sum}}}{\ln{m_{ans}}}\) 分。
这题出到这里可以结束了。但出题人为了验证你的 \(m\) 是算的还是蒙的，又给了 \(Q\) 次操作，每次操作中：
然后交互库向第一个函数输入一个 \([0,m-1]\) 内 \(\text{long long}\) 类型的数，你可以用任意加密手段，将该数加密成一个 \(n\) 位 \(01\) 字符串并返回给交互库。
接着交互库向第二个函数输入你刚才加密得到的 \(n\) 位的字符串，这个字符串有可能被交互库恶搞，导致该串所有位取反，然后整个串反转。你需要用适当的解密手段，将其解密为一开始向第一个函数输入的 \(\text{long long}\) 类型的数，并返回给交互库。
每次操作后，交互库会判断第二个函数返回的数 是否和一开始向第一个函数输入的数一样。

一旦有一次操作加密前的数和解密后的数不一样，你就得不到解密分数，即之前根据 \(m\) 得的分数打折 \(20\%\)。

subtask1 (30pts)：\(n\le 18\)
subtask2 (70pts)：\(n\le 60\)
对于所有数据，\(0\le Q\le 50000\)

由于交互题描述很长，我懒得一字不差地搬完，下面放上完整题面，但问题描述写得有点恶心，我一开始没看懂

Solution

先算出 \(m\)。

先考虑 \(n\) 是奇数的情况。
显然翻转之后正中间的一个 bit 会取反，此时