YBT11 错排问题

题解

　　　我们设fi表示1-i的满足条件的排列个数，考虑如何转移。

　　　不难发现fi 与 fi-1只多了i这个数，问题就是i应该放在哪一个位置。

　　　容易想到i显然不能放在第i个数，不合法。所以i一定是与前面某个数交换位置的， 假设这个数是a。

　　　假设a是不合法的， 与i交换显然合法， a是合法的交换后仍然合法， 所以a可以合法序列中的任意一个数，也可以是某个序列中唯一一个不合法的元素。

　　　考虑情况1：a是合法的， 由于原来一共有fi-1个合法序列， 其中每个序列的i-1个元素都是合法的， 共有fi-1*(i-1)个可以交换的a，

　　　考虑情况2：对于每个可能的a, a是唯一不合法的，也就是除了a均合法， 那么有fi-2种情况（读者可仔细思考）， 同时前面的i-1个元素都可以是a，  所以共有fi-2*(i-1)个

　　　综上： 

　　　　　

code:

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;

const int N = 100;
int n, f[N];

signed main(){
    scanf("%d", &n);
    f[1]=0;f[2]=1;
    for(int i=3; i<=n; i++) f[i] = f[i-1]*(i-1) + f[i-2]*(i-1);
     printf("%lld", f[n]);
    return 0;
}