定义

一个序列里所有数都不在他原本位置上就叫错排。
例：写信时将n封信封装入不同的信封中，全部装错的情况有多少种。

递推公式

f[n]：$n$个元素都不在对应位置上的方法数。

第一步：把第$n$个元素放在任意一个位置，假设为位置$k$，则有$n-1$种放法。

第二步：放元素$k$，这时有两种情况
1. 放在位置$n$，这时还剩 $n-2$ 个元素，就有f[n - 2]种方法。
2. 不放在位置$n$，这时还有$n-1$ 个元素，就有f[n - 1]种方法。

得：$f[n] = (n - 1) \times (f[n - 1] + f[n - 2])$
特别的： $f[1] = 0$，$f[2] = 1$

代码模板

f[1] = 0;
f[2] = 1;
for(int i = 3; i <= n; i ++)
    f[i] = (i - 1) * (f[i - 1] + f[i - 2]);

可以看出这是个DP问题。

例题

http://codeforces.com/problemset/problem/888/D

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e7;

LL f[N];

LL C(LL a, LL b)
{
    LL x = 1, y = 1;
    for(int i = 1; i <= b; i ++)
    {
        x *= (a - i + 1);
        y *= i;
    }
    return x / y;
}

int main()
{
    int n, k;
    cin >> n >> k;
    LL ans = 1;
    f[2] = 1;
    for(int i = 2; i <= k; i ++)
    {
        if(i > 2) f[i] = (i - 1) * (f[i - 2] + f[i - 1]);
        ans += C(n, i) * f[i];
    }
    cout << ans << endl;

    return 0;
}