Question

C语言POJ的一个题目算法没看懂，求帮忙。。。

题目大意:1..n的一个排列{An}被称作完美排列，等价于数列{|Ai - i|}是0..n-1的一个排列。对于指定的n≤1000，给出一个完美排列或者输出0表示不存在1..n的完美排列。 这个MS是罗马尼亚数学竞赛的题…… 如果作为ACM问题的话最合适的做法是搜小数据然后找规律 >_< 不过这显然不是我们研究科学问题的态度……下面给出一个带证明的做法。 首先我们证明，当且仅当n ≡ 0, 1 (mod 4)的时候存在1..n的完美排列。 首先，由于{|Ai - i|}是0..n-1的一个排列，所以∑|Ai - i| = n(n-1)/2。 同时，∑|Ai - i| ≡ ∑(Ai - i) = ∑Ai - ∑i = 0 (mod 2)。 故n(n - 1)/2 ≡ 0 (mod 2)。这样就得到n ≡ 0, 1 (mod 4)。 下面我们构造满足题意的解: 我们把排列看做置换。 n ≡ 0 (mod 4) 的时候，一个可行的置换是轮换(1, n, 2, n - 1, 3, n - 2, ..., n/4, 3n/4 + 1, n/4 + 1, 3n/4 - 1, ..., n/2 - 1, n/2 + 1, n/2)。 3n/4 为这个置换的唯一不动点。 n ≡ 1 (mod 4) 的时候，设s = n - 1，一个可行的置换是轮换(1, n, 2, n - 1, 3, n - 2, ..., s/4, 3s/4 + 2, s/4 + 1, 3s/4, s/4 + 2, 3s/4 - 1, ..., s/2, s/2 + 1)。 而3s / 4 + 1为这个置换的唯一不动点。 这就证明完毕。于是这个题也就解决了。 代码就不贴了。 当且仅当n ≡ 0, 1 (mod 4)是什么意思啊 整个算法有谁还能简单地解释下呢 证明的第三行开始都不懂了

Answer 1

≡这个是恒等于的意思，n
≡
0
(mod
4)，所以这句话的意思是n除以4余0，mod是取模运算，n关于4取模，也就是求n除以4的余数，另一句同理。
下面分类讨论了两种情况，得出了不动点，即经过映射后，是自身的点。