C语言这个算法没看懂,

问题描述:

C语言这个算法没看懂,
1..n的一个排列{An}被称作完美排列,等价于数列{|Ai - i|}是0..n-1的一个排列.对于指定的n≤1000,给出一个完美排列或者输出0表示不存在1..n的完美排列.
这个MS是罗马尼亚数学竞赛的题……
如果作为ACM问题的话最合适的做法是搜小数据然后找规律 >_
1个回答 分类:综合 2014-11-16

问题解答:

我来补答
当且仅当n模4为0或1,也就是除以4的余数是0或1时
证明的第三行,在求和式中,因为每一对Ai和i,永远为一正一负,一同改变符号不改变模2的取值,所以模2为0
这样就证明了n ≡ 0, 1 (mod 4)
后面的构造可以看作是一个特例,满足题意的一个解
 
 
展开全文阅读
剩余:2000