简单错排问题

1.定义

n个有序的元素有n!个不同的排列，如果一个排列使得所有的元素不在原来的位置上，则称这个排列为错排（也称重排）。例如，1 2的错排是唯一的，只有1个，即2 1。1 2 3的错排有2个，即3 1 2，2 3 1。

2.错排公式

设i个有序元素的错排有Ai个，则n个有序的元素的错排个数为 An=(n-1)*(An-1+An-2)

3.公式推导

设共有n个有序元素 （1）考虑第n个元素，如果将其放在某一个位置，一共有n-1种情况； （2）考虑第i(1≤iC; while(C--){ sum=1; cin>>n; if(n20){ cout