错位排序。

糊涂人寄信题目描述有一个糊涂人写了 nn 封信和 nn 个信封到了邮寄的时候把所有的信都装错了信封。求装错信封可能的种类数。输入描述有多行读入每行输入一个正整数 nn表示一种情况。(n≤20n≤20)输出描述输出相应的答案。输入输出样例示例输入1 3 4输出0 2 9import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNextInt()){ int n sc.nextInt(); System.out.println(fib(n)); } } static long fib(int n){ if(n 0 ||n 1) return 0; if(n 2) return 1; return (n - 1)*(fib(n - 1) fib(n - 2)); } }错位排序Derangement是指一个排列其中每个元素都不在它原来的位置上。通常用!n表示 n 个元素的错位排列数。简单推导思路考虑第一个元素不能放在位置 1它可以放在位置 kk2…n。若元素 1 放在位置 k且元素 k 放在位置 1则剩下 n-2 个元素错位!(n-2)若元素 1 放在位置 k但元素 k 不放在位置 1则相当于把 k 看作新的“第一位置”元素 k 不能占位置 1剩下 n-1 个元素错位!(n-1)对每个 k 有 !(n-1)!(n-2)k 有 n-1 种选择所以得到递推式。