大难题，但是非常的有意思。思路来自 \(\color{black}\text{艾}\color{red}\text{利克斯·伟}\)。补充了一点小细节。
题意
对于一个 可重 集合 \(S\)，初始为 \(\{1 \dots n\}\)，执行以下操作：删除集合中的最大、最小元素 \(S_{min}, S_{max}\)，加入 \(S_{max} - S_{min}\)。最终集合只剩下一个元素，输出这个元素。
给定 \(T\) 组 \(n\)，分别输出答案，\(1 \le T \le 10^5, 1 \le n \le 10^9\)。
做法
首先观察题目给出的操作序列，容易发现这些操作是分为两部分的。记第 \(i\) 次操作加入的是 \(a_i - b_i\)。存在一个 \(p\) 使得 \(\forall 1 \le i < p\)，\(a_i > 2b_i\)，并且 \(a_p \le 2b_p\)。那么 \(\forall 1 \le i \le p, b_i = i, a_{i-1} - a_i \in \{0, 1\}\)，看起来是很可以做的。
这部分先按下不表，转而考察 \(p < i \le n-1\) 的情况。记第 \(p\) 次操作以后的可重集合是 \(S'\)，同时也记它为集合排序后的序列。那么容易得出此时的每次操作以后，新集合的最小值一定是刚加入的数。这个直觉的来源是，加入的数整体而言在不断变小。事实上可以证明，由于最大值不减，所以每两轮，加入的数一定不减；而第 \(p\) 和 \(p+1\) 次操作都保证生成的数是集合最小值——所以接下来的过程中它始终保持最小。有了这个结论，我们可以优美地描述后半部分操作：\(Ans = S'_2 - (S'_3 - (S'_4 - \dots (S'_{n-p} - S'_1)\dots))\)。
接下来，考虑前半部分操作。首先，\(b_i = i, a_{i-1} - a_i \in \{0, 1\}\) 告诉我们，每一次生成的数都会变小 \(1\) 或 \(2\)。那么从大到小扫描值域的过程中，每次碰到的数都要么有一个要么有两个。一旦生成了一个数，这个数和它后面的所有数的个数都确定下来了。所以考虑依次确定这些数的个数。记 \(d_i = a_{i-1}-a_i\)，则若 \(d_i = 0\)，被确定的数是 \(a_i - i\) 有两个；否则被确定的是 \(a_i - i\) 有两个，\(a_i - i + 1\) 有一个。考虑维护 \(d\) 而不是 \(a\)。那么相当于我扫描到一个 \(0\) 就加入 \(10\)，扫描到一个 \(1\) 就加入 \(110\)。考虑 \(d\) 序列的前几项：
\[0/10/11010/1101101011010/... \]你可以把生成 \(d\) 的过程分段化，设 \(Q_i\) 表示第 \(i\) 阶段生成的串，那么它前缀依次拼接得到的就是 \(d\) 序列。\(Q_{i+1}\) 是由 \(Q_i\) 中所有 \(0\) 替换成 \(10\)，所有 \(1\) 替换成 \(110\) 得到的。生成这种东西，不要依次递推，而是考虑从开头插入操作。具体地，记 \(f_{0/1, i}\) 表示一开始为 \(0/1\) 进行 \(i\) 次迭代得到的东西，那么 \(Q_i = f_{0, i}\)。则存在递推：
\[\begin{cases} f_{0, i} = f_{1, i-1} + f_{0, i-1}\\ f_{1, i} = f_{1, i-1} + f_{1, i-1} + f_{0, i-1} \end{cases} \]那么我们就获得了一种优雅的方法生成 \(Q\)，可以借此获得 \(d\) 的前缀信息。
接下来，只需要结合上面对于后半部分操作的结论即可。容易得出，考虑我们在第 \(p\) 次操作结束后生成的 \(d\) 所对应的 \(a\) 序列。则上述的 \(S'_1 = a_p - p \le p\)，而 \(S'_i = a_{n-i+1}(2 \le i \le n-p)\)。所以：
\[\begin{align*} Ans &= a_{n-1} - (a_{n-2} - (a_{n-3} - \dots (a_{p+1} - (a_p - p))\dots))\\ &= (-1)^{n-p}p +\sum\limits_{i = p}^{n-1} (-1)^{n-i+1}a_i\\ &= \begin{cases} p-s_{n-1}-s_{n−3}-\dots-sp+1p−sn−1−sn−3−\dots−sp+1。 \end{cases} \end{align*} \] 标签：dots,10,CF1810H,le,Last,Number,生成,集合,操作 From： https://www.cnblogs.com/kyeecccccc/p/17495960.html