CF925C

SoyTony · 2023-10-01 21:03:53 · 题解

对于一个排列，i 位置合法的充要条件是其最高位 k 在前缀 [1,i-1] 出现次数为偶数，可以按最高位从高到低排序，这样加入时所有可能对最高位出现次数产生影响的数都已经加入了，不会出现后插入的数影响先插入的数。

每次批量加入最高位为 k 的数，一个方法是在当前序列开头以及每个第 k 位为 1 的位置后插入都加入一个最高位为 k 的数，这种加入方法说明了最高位相同的数相对顺序无关紧要。

使用链表维护当前的序列，发现第 i 次最多加入 2^{i-1} 个数，每次每次暴力遍历链表是可以接受的。

提交记录：Submission - CodeForces