(mathcal{Description})
Link.
给定 (0sim n-1) 的排列 (p_{0..n-1})，每次操作给出 (i)，交换 (p_i) 和 (p_{(i+p_i)mod n})。构造一种使排列升序的操作序列。
(nle100)。
(mathcal{Solution})
反正兔子就一个样例观察法，一个暴力伪解拍上去就 AC 了。（
先讲讲我的伪解，观察样例解释：
First, announce (i=6). We swap (P_6(=5)) and (P_{(6+5)mod8}=P_3(=6)), turning (P) into (7,1,2,5,4,0,6,3).
Then, announce (i=0). We swap (P_0(=7)) and (P_{(0+7)mod8}=P_7(=3)), turning (P) into (3,1,2,5,4,0,6,7).
Then, announce (i=3). We swap (P_3(=5)) and (P_{(3+5)mod8}=P_0(=3)), turning (P) into (5,1,2,3,4,0,6,7).
Finally, announce (i=0). We swap (P_0(=5)) and (P_{(0+5)mod8}=P_5(=0)), turning (P) into (0,1,2,3,4,5,6,7).
发现三次 (p_i=5)，一次 (p_i=7)。考虑到样例的迷惑性，我们尝试让对 (p_i=5) 的操作挨在一起。交换第一步和第二步，发现操作序列仍合法。
接下来，我们强行解释该操作序列的内在逻辑：
- 希望 (p_7=7)，反复操作 (p_i=7) 直到 (p_7=7)；
- 希望 (p_7=7land p_6=6)，反复操作 (p_i=6)（样例中不需要操作），直到不满足 (p_7=7) 回到第一步，或满足 (p_6=6)；
- 希望 (p_5=5land p_6=6land p_7=7)，操作同上。
- ……
综上，交换策略为
选择不满足 (p_i=i) 的最大的 (p_i) 进行交换直到序列升序。
然后就 AC 了，复杂度不知道。（
正解是先操作使得 (p={n-1,n-2,cdots,0}) 然后逆序。操作方法考察从后往前的每个 (i)，不断操作 (i) 直至 (p_i=n-i-1)，可证至多操作 (mathcal O(n)) 次，总复杂度 (mathcal O(n^2))。
(mathcal{Code})
伪解：
/* Clearink */
#include <cstdio>
#include <vector>
#define rep( i, l, r ) for ( int i = l, rpbound##i = r; i <= rpbound##i; ++i )
#define per( i, r, l ) for ( int i = r, rpbound##i = l; i >= rpbound##i; --i )
const int MAXN = 100;
int n, p[MAXN + 5];
std::vector<int> ans;
inline void iswp ( int& a, int& b ) { a ^= b ^= a ^= b; }
int main () {
scanf ( "%d", &n );
rep ( i, 0, n - 1 ) scanf ( "%d", &p[i] );
while ( true ) {
int irr = -1;
rep ( i, 0, n - 1 ) if ( i ^ p[i] && ( !~irr || p[i] > p[irr] ) ) irr = i;
if ( !~irr ) break;
ans.push_back ( irr );
iswp ( p[irr], p[( irr + p[irr] ) % n] );
}
printf ( "%d
", ( int ) ans.size () );
for ( int i: ans ) printf ( "%d
", i );
return 0;
}
正解：
/* Clearink */
#include <cstdio>
#include <vector>
#define rep( i, l, r ) for ( int i = l, rpbound##i = r; i <= rpbound##i; ++i )
#define per( i, r, l ) for ( int i = r, rpbound##i = l; i >= rpbound##i; --i )
const int MAXN = 100;
int n, p[MAXN + 5];
std::vector<int> ans;
inline void iswp ( int& a, int& b ) { a ^= b ^= a ^= b; }
inline void oper ( const int i ) {
ans.push_back ( i ), iswp ( p[i], p[( i + p[i] ) % n] );
}
int main () {
scanf ( "%d", &n );
rep ( i, 0, n - 1 ) scanf ( "%d", &p[i] );
per ( i, n - 1, 1 ) for ( ; p[i] != n - i - 1; oper ( i ) );
per ( i, n - 2, 0 ) {
rep ( j, i + 1, n - 2 ) oper ( j );
oper ( i ), oper ( i );
}
printf ( "%d
", ( int ) ans.size () );
for ( int i: ans ) printf ( "%d
", i );
return 0;
}