题目描述 Description
转眼毕业了，曾经朝夕相处的同学们不得不都各奔东西，大家都去了不同的城市开始新的生活。在各自城市居住了一段时间后，他们都感到了一些厌倦，想去看看其他人的生活究竟如何，于是他们都选择到另一个同学所在城市去旅游，并且希望旅游的城市各不相同，他们想知道有多少种不同的方案，可是数量实在太多了，他们无法计算出来，你能帮助他们吗。
输入输出格式 Input/output
输入格式：
一个正整数n(n<200)，表示人数。
输出格式：
输出格式：
一个数，表示有多少不同的方案。
输入输出样例 Sample input/output
样例测试点#1
输入样例：
3
输出样例：
2
- 提示：
- 有如下两种方案：
同学1去同学2的城市，同学2去同学3的城市，同学3去同学1的城市。
同学1去同学3的城市，同学3去同学2的城市，同学2去同学1的城市。
思路：
为了简化题目，以下我用“元素”表示每位同学，用“位置”表示他们所到达的城市，当n个元素放在n个位置，我们可以用D(n)表示元素与位置各不对应的方法数，那么D(n-1)就表示n-1个元素放在n-1个位置，D(n-1)则表示n-1个元素所产生的的各不对应的方法数，以此类推：
第一步：我们可以把第n个元素放在一个位置k，一共有n-1种放法。
第二步：放编号为k的元素，这时候就会出现两种情况：
①将它放到n原来所在的位置，那么对于剩下的n-1个元素，因为第k个元素放到了位置n，剩下n-2个元素就会有D(n-2)种放法；
②那么第k个元素不把它放到n原来所在的位置，而是放到其他的位置，这时候，对于这n-1个元素，就会出现D(n-1)种放法
总的来说，n不能移动到自己所在的位置，所以总的移动次数应该是n-1次，因此，递推公式就是两种情况的综合再乘以要移动的元素个数，即：D(n)=(n-1)[D(n-1)+D(n-2)]，这个递推式就是有名的错排问题
特殊情况：当n=1时，D(n)=0；当n=2时，D(n)=1
所以这题就可以变得十分简单了，但写完代码你会发现，当n=13时，就会超出int范围，所以必须使用高精度算法求解，我为了偷懒，就没有打高精度的代码，以下就是我直接根据公式写出来的代码。
代码如下：
#include <stdio.h>
int D(int n)
{
if(n==) return ;
else if(n==) return ;
else return (D(n-)+D(n-))*(n-);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",D(n));
return ;
}