CVBB ACM Team

• 日期：2020.7.27

• 比赛地址： 传送门

• 做题情况：lxh(-)，tyx(EJK)，gyp(BC)

构造一个$1$到$n$的排列，使对于任意$1 \le i \le n$，可以从这个排列中取出一个连续的长度为$i$的部分，它们的和$\mod \ n = k$，若没有解输出-1

$1 \le n \le 5000$，$0 \le k < n$

首先我们发现$n$是奇数的时候必须有$k=0$，$n$是偶数的时候必须有$k=\frac{n}{2}$，其余情况均无解。$n$是奇数的时候，构造$n,1,n-1,2,n-2 \ldots$，$n$是偶数时构造$n,\frac{n}{2},1,n-1,2,n-2 \ldots$即可

有一个排列$1,2 \ldots n$，$m$次操作，每次操作对其做$x$次$K$-约瑟夫变换，问最后这个排列是什么，$K$-约瑟夫变换的意思是，每次进行约瑟夫游戏，并依次将出局的人放到下一个排列

$1 \le n,m \le 10^5$，$n \times m \le 10^6$，$1 \le k \le n$，$1 \le x \le 10^9$

$K$-约瑟夫变换本质也是一个置换，这个置换是固定的，所以我们对于每个环可以将其长度$\mod \ K$，这样我们可以在$O(len)$时间处理每个环变成了什么样，至于约瑟夫变换，可以每次通过在平衡树里query相应位置的数在$O(n \log n)$的时间内解决，因此总复杂度为$O(nm \log n)$

第一小时：

第二小时：

第三小时：

第四小时：

第五小时：