本文共 761 字，大约阅读时间需要 2 分钟。

错排问题

题目链接：

题目描述

解题思路

这道题是一道入门级（个鬼）的递推。

我们将第 $n$ 个数放在第 $k$ 个位置上，则有 $n-1$ 中放法（$n!=k$）。

余下的元素有两种情况：

• 将 $k$ 放在 $n$ 上，则剩下的元素为 $n-2$ 的错排，即 $f_{n-2}$。
• 将 $k$ 放在非 $n$ 的位置上，则包括 $k$ 在内剩下的元素为 $n-1$ 的错排，即 $f_{n-1}$。

因为我们是在确定 $n$ 的位置之后再考虑 $k$ 的情况，所以 $n$ 的情况和 $k$ 的情况满足乘法原理。

因为 $k$ 放 $n$ 与不放 $n$ 是两种不同的情况，所以这两种情况满足加法原理。

得递推式为：$$f_n=(n+1)(f_{n-1}+f_{n-2})$$

code

#include
   
    #include
    
     #define int long longusing namespace std;int n;int f[30];signed main(){   	cin>>n;	f[1]=0,f[2]=1;	for(int i=3;i<=n;i++)		f[i]=(i-1)*(f[i-1]+f[i-2]);	cout<
     
      <