题解

思路

一次操作会令总和增加 $T=N(N+1)/2$。

做法

因此可行的必要条件是存在整数 $M$ 使 $S+MT$ 能被 $N$ 整除：当 $N$ 为奇数时只能有 $S\equiv0\pmod N$；当 $N$ 为偶数时还允许 $S\equiv N/2\pmod N$。这个条件也充分。若当前总和还不能被 $N$ 整除，先加入排列 $(1,2,\ldots,N)$，此后平均数为整数。

设当前有一项高于平均数、一项低于平均数。构造排列 $P$，令这两个位置分别取 $1,2$，其余位置任意填入 $3$ 到 $N$；再令 $Q_i=N+1-P_i$，并交换高、低两个位置的 $Q$ 值。两次操作后，其余位置都增加 $N+1$，高位只增加 $N$，低位增加 $N+2$，也就是在忽略所有位置共同增加的常数后把一个单位从高位转移到低位。不断执行即可使所有元素相等。

复杂度

操作次数不超过 $10^4$，构造复杂度为 $O(NM)$，其中 $M$ 为输出的操作次数。