SSOJ2231军事情报
1947+
作者：crxis 发布：2017-08-28 分类：递推
题目大意：编号为1到n的信需要分别放到编号为1到n的信封，请问每一个封信都放错信封共有多少种可能？
题目描述
俗话说，“不怕神一样的对手，就怕猪一样的队友。”虽然后世的历史学家们总是对修罗王的黑暗军团最终以惨败告终的原因争吵不休，但有一个原因是大家公认的，那就是邪狼把n封军事情报装在n个信封时，他居然全部都装错了信封。不管你信不信，反正我是信了。现在，请你算一下，所有情报都装错信封共有多少中可能？
输入
一个整数n，1<n<20。
输出
一个整数，即可能数。
样例输入
2
样例输出
1
解题思路
这种题目，数据范围n<20，很多人以外是搜索，但你会发现搜索很难剪枝优化，复杂度是n!，必定超时。其实这个20只是为了避免使用高精度而已！
下面考虑递推怎么做，先设立状态，Si表示i个信封都放错共有多少种可能。
初始条件：S0=0，S1=0，S2=1（1放到2，2放到1）
思考：n个信封，跟前面的n-1个信封有什么关系呢？
首先，第n个情报不能放在第n个信封，第n个信封只能放1到n-1个情报中的其中一个，即第n个情报和第k个情报交换位置后，还是全部放错。这个k，可以是1到n-1中的任何一个。
交换后，全部情报都放错：
要么原来前面n-1个情报全部都放错，这时n和前面n-1个任何一个情报交换位置都可以——n-1个情报都放错有S(n-1)种可能，每种可能都有n-1中交换方法，即S(n) = S(n-1) * (n-1)。
要么原来前面n-1个情报有n-2个都放错（只有一个放对），这是只能和放对的那个情报交换位置——n-2个情报都放错有S(n-2)种可能，每种可能只有一种交换方法，但放对的情报可以是1到n-1，因此S(n) = S(n-2) * (n-1)。
两种情况合并起来，即Sn = (S(n-1) + S(n-2)) * (n-1)
程序实现
