A.防诈骗
\(\text{Sol1：}\)
首先可以把这 \(n\) 个水杯划分为不交的链，对链暴力 \(\mathrm{mex}\) 之后发现很有规律，按照经典结论把所有游戏的 \(SG\) 函数求异或和，如果为 \(0\) 那么后手必胜，否则必败。
但是由于是求第 \(k\) 小满足后手必胜的 \(n\) ，所以只能拿答案 \(\le10^7\) 的 65 分。
正解与之十分类似，只不过思考的方式不同导致后面的优化比较简单。
\(\text{Sol2：}\)（搬运）
把所有除掉末尾 \(0\) 之后相同的数分为一组，每组分别考虑。
现在的问题是：有若干个游戏，每个游戏有 \(n\) 堆石子，每堆分别有 \(0,1,\cdots,n-1\) 个石子，每次的操作是选一堆石子，假设它有 \(x\) 个，那么你可以拿走其中 \(c\) 个，\(c\in[1,x]\)。如果存在一堆石子数量 \(y=x-c\)，那么把 \(x\) 和 \(y\) 都拿走。要求这个游戏的 SG 函数，如果所有游戏的 SG 函数的异或和为 \(0\)，那么后手必胜。
如果没有把 \(x,y\) 都拿走这个操作，这个游戏就是 Nim 游戏。注意到 \(x-c=y\)，\((x-c)\oplus y=0\)，拿走他们并不会影响异或和。所以可以把问题视为没有把 \(x,y\) 都拿走这个操作，因为这个操作并不影响这个游戏的 SG 函数，这样这个游戏的 SG 函数就是 \(\oplus_{i=0}^{n-1}i\)。
令 \(f(x)\) 表示 \(x\) 二进制下末尾 \(0\) 的个数，整个游戏的 SG 函数是 \(\oplus _{i=1}^nf(i)\)，而 \(f(i)=j\) 的 \(i\) 的数量是 \(\lfloor\frac{n}{2^j}\rfloor-\lfloor\frac{n}{2^{j+1}}\rfloor\)，我们只关心这个值的奇偶性，也就是我们只关心 \(n\) 的二进制下第 \(j\) 位和第 \(j+1\) 位是否相同。
首先二分答案 \(mid\)，求出 \(\le mid\) 的有多少个 \(n\) 满足后手必胜。然后数位 DP，设 \(f_{i,j,s,flag}\) 分别表示从高到低填完了 \(i\) 位，第 \(i\) 位填的是 \(j(j\in\{0,1\})\)，现在的异或和是 \(s\)，前 \(i\) 位是否顶 \(mid\) 的上界。状态数 \(O(\log^2 n)\)，转移 \(O(1)\)。加上二分，总复杂度 \(O(T\log^3 n)\)