【错排】数学公式

这道题的数学公式是错排公式，也称为derangement formula。
错排公式给出了将 n 个元素全部错排的方案数。记为 D(n) 或 !n。

数学公式为：

D(n) = n! * (1/0! - 1/1! + 1/2! - 1/3! + ... + (-1)^n * 1/n!)

其中，n! 表示 n 的阶乘，而 (-1)^n 表示取 n 的符号。
例如，D(3) = 3! * (1/0! - 1/1! + 1/2! - 1/3!) = 3 * (1 - 1 + 1/2 - 1/6) = 3

对于本题来说，如果题目要求求解 n 个人全装错信的方案数，即为 D(n)。

完整代码：

#include <iostream>
using namespace std;
long long int derangement(long long int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    if (n == 2) return 1;
    long long int dp[n+1];
    dp[0] = 1;
    dp[1] = 0;
    dp[2] = 1;
    for (int i = 3; i <= n; i++) {
        dp[i] = (i - 1) * (dp[i-1] + dp[i-2]);
    }
    return dp[n];
}
int main() {
    int n;
    cin >> n;
    long long int result = derangement(n);
    cout << result << endl;
    return 0;
}